2016 Multi-University Training Contest 4 team170

README.md

2016 Multi-University Training Contest 4 team170

A.cpp

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>

using namespace std;

char s[100101],t[100101];
int nxt[100101];
int ans[100101];
int dp[100101];
const int mod=1000000007;
int T;

int main(){
	dp[0]=1;
	scanf("%d",&T);
	for(int tt=1;tt<=T;++tt){
		scanf("%s%s",s+1,t+1);
		int N=strlen(s+1),M=strlen(t+1);
		for(int i=2;i<=M;++i){
			int j=nxt[i-1];
			while(j&&t[j+1]!=t[i]) j=nxt[j];
			if(t[j+1]==t[i]) nxt[i]=j+1;
			else nxt[i]=0;
		}
		for(int i=1;i<=N;++i){
			int j=ans[i-1];
			dp[i]=dp[i-1];
			while(j&&s[i]!=t[j+1]) j=nxt[j];
			if(s[i]==t[j+1]) ans[i]=j+1;
			else ans[i]=0;
			if(ans[i]==M){
				ans[i]=nxt[ans[i]];
				dp[i]+=dp[i-M];
				if(dp[i]>=mod) dp[i]-=mod;
			}
		}
		printf("Case #%d: %d\n",tt,dp[N]);
	}
	return 0;
}

B.cpp

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>

using namespace std;

int T,N;
vector<int> V[100100];
int cntv[100100];
int st[100100];
int ed[100100];
int links[100100];
int same[100100][3];
int fa[100100];
int A[100100];
int ans[100100];
int anss[100100];
bool solved;
int stand[100100];

inline bool Cmp(){
	for(int i=1;i<=N;++i) if(ans[i]!=anss[i]) return anss[i]<ans[i];
	return false;
}

bool checkFa(int L,int R){
	bool flag=true;
	for(int i=L;i<R;++i){
		if(fa[links[i]]!=links[i+1]){
			flag=false;
			break;
		}
	}
	if(flag) return true;
	flag=true;
	reverse(links+L,links+R+1);
	for(int i=L;i<R;++i){
		if(fa[links[i]]!=links[i+1]){
			flag=false;
			break;
		}
	}
	return flag;
}

void checkRoot(int R){
	fa[R]=-1;
	{
		stack<int> S;
		S.push(R);
		while(!S.empty()){
			int x=S.top();
			S.pop();
			for(int i=0;i<int(V[x].size());++i) if(V[x][i]!=fa[x]){
				if(A[V[x][i]]>A[x]) return;
				fa[V[x][i]]=x;
				S.push(V[x][i]);
			}
		}
	}
	for(int i=1;i<=N;++i) if(cntv[i]&&!checkFa(st[i],ed[i])) return;
	{
		priority_queue<int> PQ;
		for(int i=N;i>=1;--i){
			if(!cntv[i]){
				if(PQ.empty()) return;
				anss[PQ.top()]=i;
				PQ.pop();
			}
			else{
				anss[links[st[i]]]=i;
				for(int j=st[i]+1;j<=ed[i];++j) PQ.push(links[j]);
			}
		}
	}
	if(!solved||Cmp()){
		for(int i=1;i<=N;++i) ans[i]=anss[i];
		solved=true;
	}
}

void solve(){
	solved=false;
	for(int i=1;i<=N;++i){
		++cntv[A[i]];
		for(int j=0;j<int(V[i].size());++j){
			if(A[V[i][j]]==A[i]){
				if(same[i][0]==2){
					printf(" Impossible\n");
					return;
				}
				same[i][++same[i][0]]=V[i][j];
			}
		}
		if(stand[A[i]]==-1||same[stand[A[i]]][0]>same[i][0]){
			stand[A[i]]=i;
		}
	}
	st[0]=1,ed[0]=0;
	for(int i=1;i<=N;++i){
		st[i]=ed[i-1]+1,ed[i]=ed[i-1];
		if(stand[i]==-1) continue;
		{
			int pre=-1;
			int now=stand[i];
			int len=0;
			int nxt=-1;
			do{
				links[++ed[i]]=now;
				nxt=-1;
				for(int j=1;j<=same[now][0];++j) if(same[now][j]!=pre){
					nxt=same[now][j];
				}
				++len;
				pre=now;
				now=nxt;
			}while(now!=-1);
			if(len!=cntv[i]){
				printf(" Impossible\n");
				return;
			}
		}
	}
	if(cntv[N]==0){
		printf(" Impossible\n");
		return;
	}
	{
		int f=links[st[N]],g=links[ed[N]];
		checkRoot(f);
		if(f!=g) checkRoot(g);
	}
	if(!solved){
		printf(" Impossible\n");
	}
	else{
		for(int i=1;i<=N;++i) printf(" %d",ans[i]);
		printf("\n");
	}
}
int main(){
	scanf("%d",&T);
	for(int tt=1;tt<=T;++tt){
		scanf("%d",&N);
		for(int i=1;i<=N;++i) V[i].clear(),same[i][0]=0,cntv[i]=0,stand[i]=-1;
		for(int i=1;i<=N;++i) scanf("%d",A+i);
		for(int i=1;i<N;++i){
			int x,y;
			scanf("%d%d",&x,&y);
			V[x].push_back(y);
			V[y].push_back(x);
		}
		printf("Case #%d:",tt);
		solve();
	}
	return 0;
}

C.cpp

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>

using namespace std;

int nei[21];
int T,N,M;
int cnt[1048580];
int tot;
int inv[1048580];
int e[400][2];

bool bfs(int mask){
	if(!mask) return false;
	int nmask=mask&-mask;
	int qmask=mask&-mask;
	while(qmask){
		int f=inv[qmask&-qmask];
		qmask^=1<<f;
		int fmask=(nmask|nei[f])&mask;
		qmask|=fmask^nmask;
		nmask=fmask;
	}
	return nmask==mask;
}

void dfs(int st,int op1,int op2){
	if(st==N){
		if(bfs(op1)&&bfs(op2)){
			++tot;
			++cnt[op1];
			++cnt[op2];
		}
		return;
	}
	dfs(st+1,op1|(1<<st),op2);
	dfs(st+1,op1,op2|(1<<st));
}

int main(){
	for(int i=0;i<20;++i) inv[1<<i]=i;
	scanf("%d",&T);
	for(int tt=1;tt<=T;++tt){
		scanf("%d%d",&N,&M);
		tot=0;
		for(int i=0;i<N;++i) nei[i]=0;
		for(int i=0;i<M;++i){
			int x,y;
			scanf("%d%d",&x,&y);
			nei[x]|=1<<y;
			nei[y]|=1<<x;
			e[i][0]=x,e[i][1]=y;
		}
		for(int i=0;i<(1<<N);++i) cnt[i]=0;
		dfs(1,1,0);
		for(int i=1;i<(1<<N);i<<=1){
			for(int j=0;j<(1<<N);++j){
				if(j&i) cnt[j^i]+=cnt[j];
			}
		}
		printf("Case #%d:",tt);
		for(int i=0;i<M;++i) printf(" %d",tot-cnt[(1<<e[i][0])|(1<<e[i][1])]);
		printf("\n");
	}
	return 0;
}

D_part.cpp

#include <cstdio>
#include <cstring>

const int MOD = (int)1e9 + 7;

void update(int& x, int a)
{
    x += a;
    if (x >= MOD) {
        x -= MOD;
    }
}

const int N = 20;

int t, ways[2][1 << N + 1];

int inverse(int a)
{
    return a == 1 ? 1 : (long long)(MOD - MOD / a) * inverse(MOD % a) % MOD;
}

void gao(int n, int i, int must = -1)
{
    for (int j = 0; j < n; ++ j) {
        t ^= 1;
        memset(ways[t], 0, sizeof(*ways[t]) << n + 1);
        for (int msk_ = 0; msk_ < 1 << n + 1; ++ msk_) {
            int msk = j ? msk_ : msk_ << 1;
            if (ways[t ^ 1][msk_]) {
                update(ways[t][msk & ~(1 << j)], ways[t ^ 1][msk_]);
                if (j && !(msk >> j - 1 & 7) && (j < n - 1 || must != 0)) {
                    update(ways[t][msk | 7 << j - 1], ways[t ^ 1][msk_]);
                }
            }
        }
    }
}

int solve(int n)
{
    int n2 = n + 2 >> 1;
    memset(ways[t], 0, sizeof(*ways[t]) << n + 1);
    ways[t][0] = 1;
    for (int i = 0; i < n2; ++ i) {
        gao(n, i);
    }
    int result = 0;
    for (int msk_ = 0; msk_ < 1 << n + 1; ++ msk_) {
        bool valid = true;
        for (int i = 0; i < n; ++ i) {
            valid &= (msk_ >> i & 1) == (msk_ >> n - 1 - i & 1);
        }
        if (valid) {
            update(result, ways[t][msk_]);
        }
    }
    for (int i = n2; i < n; ++ i) {
        gao(n, i);
    }
    for (int msk_ = 0; msk_ < 1 << n + 1; ++ msk_) {
        update(result, ways[t][msk_]);
    }
    return (long long)result * inverse(4) % MOD;
}

int result[N + 1];

int main()
{
    for (int n = 1; n <= N; ++ n) {
        result[n] = solve(n);
    }
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++ t) {
        int n;
        scanf("%d", &n);
        printf("Case #%d: %d\n", n, result[n]);
    }
}

E.cpp

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>

using namespace std;

int T;
int N;
long long L,R;
int P[16][2];
long long ans;
long long powMod(long long a,long long b,long long P){
	a%=P;
	long long ret=1;
	while(b){
		if(b&1) if(P<=(ret*=a)) ret%=P;
		if(P<=(a*=a)) a%=P;
		b>>=1;
	}
	return ret;
}
long long getV(long long x,long long mod,long long rem){
	if(x<rem) return 0;
	return (x-rem)/mod+1;
}
void solve(long long mod,long long rem,int st,int add){
	ans+=add*(getV(R,mod,rem)-getV(L,mod,rem));
	for(int i=st;i<=N;++i){
		long long inv=powMod(mod,P[i][0]-2,P[i][0]);
		long long diff=P[i][1]-rem%P[i][0];
		if(diff<0) diff+=P[i][0];
		inv=inv*diff%P[i][0];
		solve(mod*P[i][0],rem+mod*inv,i+1,-add);
	}
}

int main(){
	scanf("%d",&T);
	for(int tt=1;tt<=T;++tt){
		scanf("%d%I64d%I64d",&N,&L,&R),--L;
		for(int i=1;i<=N;++i){
			scanf("%d%d",P[i],P[i]+1);
		}
		ans=0;
		solve(7,0,1,1);
		printf("Case #%d: %I64d\n",tt,ans);
	}
	return 0;
}

F.cpp

#include <cstdio>
#include <cstring>
#include <iostream>

const int N = 100000;
const int C = 26;

char buffer[N + 1];

struct State {
    int length;
    State *parent;
    State* go[C];

    State* extend(State*, int);
};

int state_count;
State states[N * 2 + 1];

State* new_state(int length)
{
    State* n = states + (state_count ++);
    n->length = length;
    n->parent = NULL;
    memset(n->go, 0, sizeof(n->go));
    return n;
}

State* State::extend(State* start, int token) {
    State *p = this;
    State *np = new_state(length + 1);
    while (p && !p->go[token]) {
        p->go[token] = np;
        p = p->parent;
    }
    if (!p) {
        np->parent = start;
    } else {
        State *q = p->go[token];
        if (p->length + 1 == q->length) {
            np->parent = q;
        } else {
            State *nq = new_state(p->length + 1);
            memcpy(nq->go, q->go, sizeof(q->go));
            nq->parent = q->parent;
            np->parent = q->parent = nq;
            while (p && p->go[token] == q) {
                p->go[token] = nq;
                p = p->parent;
            }
        }
    }
    return np;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++ t) {
        scanf("%s", buffer);
        char x = *buffer;
        scanf("%s", buffer);
        state_count = 0;
        State* root = new_state(0);
        long long result = 0;
        State* p = root;
        int last = -1;
        for (int i = 0; buffer[i]; ++ i) {
            if (buffer[i] == x) {
                last = i;
            }
            p = p->extend(root, buffer[i] - 'a');
            result += i + 1 - std::max(p->parent->length, i - last);
        }
        std::cout << "Case #" << t << ": " << result << std::endl;
    }
}

G.cpp

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <climits>
#include <utility>
#include <vector>

#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)

const int N = 100000;

int n, dfs_count, position[N], size[N], same[N];
std::vector<int> tree[N];
std::vector<std::pair<int, int> > starts[N];

void prepare(int p, int u)
{
    position[u] = dfs_count ++;
    size[u] = 1;
    foreach (iterator, tree[u]) {
        int v = *iterator;
        if (v != p) {
            prepare(u, v);
            starts[u].push_back(std::make_pair(position[v], v));
            size[u] += size[v];
        }
    }
}

typedef std::pair<int, int> Interval;

bool is_ancestor_of(int a, int d)
{
    return position[a] <= position[d] && position[d] + size[d] <= position[a] + size[a];
}

std::vector<Interval> get_intervals(int from, int to)
{
    std::vector<Interval> result;
    if (is_ancestor_of(from, to)) {
        std::vector<std::pair<int, int> >& start = starts[from];
        std::vector<std::pair<int, int> >::iterator iterator = std::upper_bound(start.begin(), start.end(), std::make_pair(position[to], INT_MAX));
        iterator --;
        int v = iterator->second;
        result.push_back(std::make_pair(0, position[v]));
        result.push_back(std::make_pair(position[v] + size[v], n));
    } else {
        result.push_back(std::make_pair(position[from], position[from] + size[from]));
    }
    return result;
}

struct Event
{
    Event(int y1, int y2, int w) : y1(y1), y2(y2), w(w)
    {
    }

    int y1, y2, w;
};

std::vector<Event> events[N + 1];

void add_events(const std::vector<Interval>& begins, const std::vector<Interval>& ends, int weight)
{
    foreach (b, begins)
    {
        foreach (e, ends)
        {
//printf("[%d, %d) * [%d, %d) = %d\n", b->first, b->second, e->first, e->second, weight);
            events[b->first].push_back(Event(e->first, e->second, weight));
            events[b->second].push_back(Event(e->first, e->second, -weight));
        }
    }
}

int delta[N << 1], maximum[N << 1];

int get_id(int l, int r)
{
    return l + r | l != r;
}

void cover(int l, int r, int a, int b, int c)
{
    if (b < l || r < a) {
        return;
    }
    int id = get_id(l, r);
    if (a <= l && r <= b) {
        delta[id] += c;
        maximum[id] += c;
    } else {
        int m = l + r >> 1;
        cover(l, m, a, b, c);
        cover(m + 1, r, a, b, c);
        maximum[id] = std::max(maximum[get_id(l, m)], maximum[get_id(m + 1, r)]) + delta[id];
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++ t) {
        int m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++ i) {
            tree[i].clear();
            starts[i].clear();
        }
        for (int i = 0; i < n - 1; ++ i) {
            int a, b;
            scanf("%d%d", &a, &b);
            a --;
            b --;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        dfs_count = 0;
        memset(same, 0, sizeof(*same) * n);
        prepare(-1, 0);
        for (int i = 0; i <= n; ++ i) {
            events[i].clear();
        }
        for (int i = 0; i < m; ++ i) {
            int from, to, weight;
            scanf("%d%d%d", &from, &to, &weight);
            from --;
            to --;
            if (from == to) {
                same[from] += weight;
            } else {
                std::vector<Interval> begins = get_intervals(from, to);
                std::vector<Interval> ends = get_intervals(to, from);
                add_events(begins, ends, weight);
            }
        }
        int total = 0;
        for (int i = 0; i < n; ++ i) {
            if (same[i]) {
                total += same[i];
                foreach (iterator, tree[i]) {
                    std::vector<Interval> intervals = get_intervals(*iterator, i);
                    add_events(intervals, intervals, -same[i]);
                }
            }
        }
        int result = INT_MIN;
        memset(delta, 0, sizeof(*delta) * (n << 1));
        memset(maximum, 0, sizeof(*maximum) * (n << 1));
        for (int i = 0; i < n; ++ i) {
            foreach (iterator, events[i]) {
                cover(0, n - 1, iterator->y1, iterator->y2 - 1, iterator->w);
            }
            result = std::max(result, total + maximum[get_id(0, n - 1)]);
        }
        printf("Case #%d: %d\n", t, result);
    }
}

H.cpp

#include <cassert>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <map>

#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)

const int H = 10;
const int M = 4;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;

typedef std::vector<int> State;

int w, part[1 << M];
std::map<int, int> transfer[1 << M][1 << M];
std::map<State, int> ways[2];

void update(int &x, int a)
{
    x = std::min(x, a);
}

State go(const State& s, int board)
{
    State ns(1 << w, INF);
    for (int mask = 0; mask < 1 << w; ++ mask) {
        foreach (iterator, transfer[mask][board]) {
            update(ns[iterator->first], s[mask] + iterator->second);
        }
    }
    return ns;
}

void add(int& x, int a)
{
    x += a;
    if (x >= MOD) {
        x -= MOD;
    }
}

std::map<int, int> result[M + 1][H + 1];

int main()
{
    for (w = 1; w <= M; ++ w) {
        for (int mask = 0; mask < 1 << w; ++ mask) {
            part[mask] = 0;
            for (int i = 0; i < w; ++ i) {
                if ((mask >> i & 1) && (!i || (~mask >> i - 1 & 1))) {
                    part[mask] ++;
                }
            }
        }
        for (int from = 0; from < 1 << w; ++ from) {
            for (int board = 0; board < 1 << w; ++ board) {
                std::map<int, int>& T = transfer[from][board];
                for (int tmp = 0; tmp < 1 << w; ++ tmp) {
                    int cost = part[board ^ tmp];
                    for (int i = 0; i < w && ~cost; ++ i) {
                        if ((from >> i & 1) && (~tmp >> i & 1)) {
                            cost = -1;
                        }
                    }
                    if (~cost) {
                        assert(cost >= 0);
                        for (int target = tmp; ; target = target - 1 & tmp) {
                            if (!T.count(target)) {
                                T[target] = INF;
                            }
                            T[target] = std::min(T[target], cost + __builtin_popcount(tmp ^ target));
                            if (!target) {
                                break;
                            }
                        }
                    }
                }
            }
        }
        State init_state(1 << w, INF);
        ways[0].clear();
        init_state[0] = 0;
        ways[0][init_state] = 1;
        for (int h = 1; h <= H; ++ h) {
//printf("ROW %d: \n", h);
            ways[h & 1].clear();
            foreach (iterator, ways[h + 1 & 1]) {
                for (int board = 0; board < 1 << w; ++ board) {
                    add(ways[h & 1][go(iterator->first, board)], iterator->second);
                }
            }
            foreach (iterator, ways[h & 1]) {
//printf("{%d,%d,%d,%d},",w,h,iterator->first[0],iterator->second);
                add(result[w][h][iterator->first[0]], iterator->second);
//for (int mask = 0; mask < 1 << w; ++ mask) {
//    for (int i = 0; i < w; ++ i) {
//        printf("%d", mask >> i & 1);
//    }
//    printf(":%d,", iterator->first[mask]);
//}
//printf("%d\n", iterator->second);
            }
            // foreach (iterator, result[w][h]) {
            //     printf("{%d,%d,%d,%d},", w, h, iterator->first, iterator->second);
            // }
        }
    }
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++ t) {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        int rr = 0;
        foreach (iterator, result[n][m]) {
            if (iterator->first <= k) {
                add(rr, iterator->second);
            }
        }
        printf("Case #%d: %d\n", t, rr);
    }
}

I.cpp

#include <cstdio>
#include <queue>
#include <vector>

const int INF = 1000000000;

template<typename Type>
class Network
{
public:
    Network(int n) : n(n), head(n, -1)
    {
    }

    void add_edge(int u, int v, Type w)
    {
        add_edge_(u, v, w);
        add_edge_(v, u, 0);
    }

    Type max_flow(int source, int target)
    {
        Type result = 0;
        while (true) {
            std::vector<int> level(n, -1);
            level.at(target) = 0;
            std::queue<int> queue;
            queue.push(target);
            while (!queue.empty() && !~level.at(source)) {
                int v = queue.front();
                queue.pop();
                for (int iterator = head.at(v); ~iterator; ) {
                    Edge& edge = edges.at(iterator);
                    int u = edges.at(iterator).to;
                    if (edges.at(iterator ^ 1).capacity > 0 && !~level.at(u)) {
                        level.at(u) = level.at(v) + 1;
                        queue.push(u);
                    }
                    iterator = edge.next;
                }
            }
            if (!~level.at(source)) {
                break;
            }
            std::vector<int> current_head(head);
            result += dfs(level, current_head, source, target, INF);
        }
        return result;
    }

private:
    struct Edge
    {
        Edge(int to, Type capacity, int next) : to(to), capacity(capacity), next(next) {}

        int to;
        Type capacity;
        int next;
    };

    void add_edge_(int u, int v, Type w)
    {
        edges.push_back(Edge(v, w, head.at(u)));
        head.at(u) = static_cast<int>(edges.size()) - 1;
    }

    Type dfs(const std::vector<int>& level, std::vector<int>& head, int u, int target, Type delta)
    {
        if (u == target) {
            return delta;
        }
        Type left = delta;
        for (int& iterator = head.at(u); ~iterator; ) {
            Edge& edge = edges.at(iterator);
            int v = edge.to;
            if (edge.capacity > 0 && level.at(u) == level.at(v) + 1) {
                Type ret = dfs(level, head, v, target, std::min(left, edge.capacity));
                edge.capacity -= ret;
                edges.at(iterator ^ 1).capacity += ret;
                left -= ret;
                if (!left) {
                    return delta;
                }
            }
            iterator = edge.next;
        }
        return delta - left;
    }

    int n;
    std::vector<int> head;
    std::vector<Edge> edges;
};

const int N = 100;

int a[10], b[10], sum[N], w[N][N];
char buffer[N + 1];

int main()
{
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++ t) {
        int n;
        scanf("%d%s", &n, buffer);
        for (int i = 0; i < 10; ++ i) {
            scanf("%d%d", a + i, b + i);
        }
        int result = 0;
        for (int i = 0; i < n; ++ i) {
            sum[i] = 0;
            for (int j = 0; j < n; ++ j) {
                scanf("%d", w[i] + j);
                sum[i] += w[i][j];
            }
            result += sum[i];
        }
        Network<int> network(n + 12);
        int source = n + 10;
        int target = n + 11;
        for (int i = 0; i < 10; ++ i) {
            network.add_edge(n + i, target, b[i] - a[i]);
        }
        for (int i = 0; i < n; ++ i) {
            network.add_edge(source, i, sum[i]);
            int c = buffer[i] - '0';
            network.add_edge(i, target, a[c]);
            network.add_edge(i, n + c, INF);
            for (int j = 0; j < n; ++ j) {
                if (i != j) {
                    network.add_edge(i, j, w[i][j]);
                }
            }
        }
        result -= network.max_flow(source, target);
        printf("Case #%d: %d\n", t, result);
    }
}

J.cpp

#include <algorithm>
#include <cstdio>

const int N = 100000;

int a[N], end[N + N + 1];

int main()
{
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++ t) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; ++ i) {
            scanf("%d", a + i);
        }
        int result = 0;
        int* p = end + n;
        int delta = 0;
        p[0] = -n;
        for (int i = 0; i < n; ++ i) {
            if (a[i]) {
                int length = std::lower_bound(p, p + result + 1, a[i] - delta) - p;
                if (length > result) {
                    result = length;
                    p[length] = a[i] - delta;
                } else {
                    p[length] = std::min(p[length], a[i] - delta);
                }
            } else {
                result ++;
                delta ++;
                p --;
                p[0] = -n - delta;
            }
        }
        printf("Case #%d: %d\n", t, result);
    }
}

L.cpp

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>

using namespace std;

int ans[100001];
int c[100001];
int N;
int T;
int a[100001];
inline void add(int x){
	while(x<=N) ++c[x],x+=x&-x;
}
inline int sum(int x){
	int ret=0;
	while(x) ret+=c[x],x^=x&-x;
	return ret;
}

int main(){
	scanf("%d",&T);
	for(int tt=1;tt<=T;++tt){
		scanf("%d",&N);
		for(int i=1;i<=N;++i){
			scanf("%d",a+i);
			c[i]=0;
		}
		for(int i=N;i>=1;--i){
			int r=i+sum(a[i]);
			add(a[i]);
			ans[a[i]]=r-min(a[i],i);
		}
		printf("Case #%d:",tt);
		for(int i=1;i<=N;++i) printf(" %d",ans[i]);
		printf("\n");
	}
	return 0;
}