ACM-ICPC Daejeon Regional 2016

b.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

int cnt[10005], n;

int main(){
	cin >> n;
	int sum = 0;
	for(int i=0; i<n; i++){
		int x;
		scanf("%d",&x);
		cnt[x]++;
		sum += x;
	}
	if(sum != n * (n-1) / 2){
		puts("-1");
		return 0;
	}
	int t = n;
	for(int i=n-1; i; i--){
		while(cnt[i]){
			int tmp[10005] = {};
			cnt[i]--;
			int d = t-1-i;
			for(int j=i; j && d; j--){
				int w = min(d, cnt[j]);
				cnt[j] -= w;
				tmp[j-1] += w;
				d -= w;
			}
			if(d){
				puts("-1");
				return 0;
			}
			for(int j=0; j<=i; j++) cnt[j] += tmp[j];
			t--;
		}
	}
	puts("1");
}

c.cpp

#include <cstdio>
#include <algorithm>
#include <bitset>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

int k, n;
pi a[1000005];
int cnt[1000005], cur;

void add(int x){
	if (!cnt[x]) cur++;
	cnt[x]++;
}

void del(int x){
	cnt[x]--;
	if (!cnt[x]) cur--;
}

int half(int x){
	if (x < 0) return (x - 1) / 2;
	return x / 2;
}

int main(){
	scanf("%d %d", &k, &n);
	for (int i = 0; i < n; i++){
		scanf("%d %d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	int e = 0;
	int dap = 1e9, pos = -1;
	for (int i = 0; i < n; i++){
		while (e < n && cur < k){
			add(a[e++].second);
		}
		if (cur == k){
			int p = half(a[i].first + a[e-1].first);
			int rad = max(a[e - 1].first - p, p - a[i].first);
			if (dap > rad){
				dap = rad;
				pos = p;
			}
		}
		del(a[i].second);
	}
	printf("%d", pos);
}

e.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
typedef pair<int, int> pi;

string str;
string sym[1005];
vector<int> gph[1005];
vector<string> spl;
int nxt;

void solve(int s, int e, int rt){
	if (s > e){
		puts("ERROR");
		exit(0);
	}
	int bracket = 0;
	for (int i = e; i >= s; i--){
		if (str[i] == '(') bracket--;
		if (str[i] == ')') bracket++;
		if (bracket != 0) continue;
		if (str[i] == '+' || str[i] == '-'){
			sym[rt] = str.substr(i, 1);
			nxt++;
			gph[rt].push_back(nxt);
			solve(s, i - 1, nxt);
			nxt++;
			gph[rt].push_back(nxt);
			solve(i + 1, e, nxt);
			return;
		}
	}
	bracket = 0;
	for (int i = e; i >= s; i--){
		if (str[i] == '(') bracket--;
		if (str[i] == ')') bracket++;
		if (bracket != 0) continue;
		if (str[i] == '*' || str[i] == '/'){
			sym[rt] = str.substr(i, 1);
			nxt++;
			gph[rt].push_back(nxt);
			solve(s, i - 1, nxt);
			nxt++;
			gph[rt].push_back(nxt);
			solve(i + 1, e, nxt);
			return;
		}
	}
	if (str[s] == '('){
		if (str[e] != ')'){
			puts("ERROR");
			exit(0);
		}
		solve(s + 1, e - 1, rt);
		return;
	}
	for (int i = s; i <= e; i++){
		if (str[i] < '0' || str[i] > '9'){
			puts("ERROR");
			exit(0);
		}
	}
	sym[rt] = str.substr(s, e - s + 1);
	return;
}

string dfs(int root){
	if (gph[root].size() == 0) return sym[root];
	if (gph[root].size() != 2){
		puts("ERROR");
		exit(0);
	}
	string ret = dfs(gph[root][0]) + " " + dfs(gph[root][1]) + " " + sym[root];
	spl.push_back(ret);
	return ret;
}

int main(){
	while (1){
		char t = getchar();
		if (t == -1) break;
		if (t == ' ' || t == '\n') continue;
		str.push_back(t);
	}
	solve(0, str.size() - 1, 0);
	dfs(0);
	sort(spl.begin(), spl.end(), [&](const string &a, const string &b){
		int c1 = count(a.begin(), a.end(), ' ');
		int c2 = count(b.begin(), b.end(), ' ');
		if (c1 != c2) return c1 > c2;
		return a < b;
	});
	for (int i = 0; i < spl.size() - 1; i++){
		if (spl[i] == spl[i + 1]){
			cout << spl[i] << endl;
			return 0;
		}
	}
	puts("ERROR");
}

f.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int oo = 1e9;

struct bd{
	int s, e, h, idx;
	bool operator<(const bd &c)const{
		return s < c.s;
	}
}a[100005], b[100005];

lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

int n;
pi c[200005], d[200005];

struct seg{
	vector<pi> tree[530000];
	int lim;
	void get_hull(vector<pi> &v){
		vector<pi> w = v;
		v.clear();
		for(auto &i : w){
			while(v.size() >= 2 && ccw(v[v.size()-2], v.back(), i) >= 0){
				v.pop_back();
			}
			v.push_back(i);
		}
	}
	bool inside(int n, int x, int y, int dx, int dy){
		assert(!tree[n].empty());
		int s = 0, e = tree[n].size() - 1;
		auto func = [&](const int idx){
			return 1ll * dx * (tree[n][idx].second - y) - 1ll * dy * (tree[n][idx].first - x);
		};
		while(s != e){
			int m = (s+e)/2;
			if(func(m) > func(m+1)) e = m;
			else s = m+1;
		}
		return func(s) >= 0;
	}
	void init(pi *a, int n){
		for(lim = 1; lim <= n; lim <<= 1);
		for(int i=0; i<n; i++){
			for(int j=lim+i; j; j>>=1){
				tree[j].push_back(a[i]);
			}
		}
		for(int j=1; j<lim+n; j++){
			get_hull(tree[j]);
		}
	}
	int query(int x, int y, int dx, int dy){
		int pos = 1;
		while(pos < lim){
			if(inside(2 * pos, x, y, dx, dy)) pos *= 2;
			else pos = pos * 2 + 1;
		}
		return pos - lim;
	}
}seg[2];

int query(bd *a, pi *b, int t, int x, int y, int dx, int dy){
	int j = seg[t].query(x, y, dx, dy);
	if(j == 2*n) return 0;
	if(j % 2 == 1) return a[j/2].idx;
	if(ccw(pi(x, y), pi(x + dx, y + dy), pi(b[j].first, 0)) > 0){
		return 0;
	}
	return a[j/2].idx;
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d %d",&a[i].s, &a[i].e, &a[i].h);
		a[i].idx = i+1;
	}
	sort(a, a+n);
	for(int i=0; i<n; i++){
		b[i] = a[n-1-i];
		tie(b[i].s, b[i].e) = pi(-b[i].e, -b[i].s);
		c[2*i] = pi(a[i].s, a[i].h);
		c[2*i+1] = pi(a[i].e, a[i].h);
	}
	for(int i=0; i<2*n; i++){
		d[i] = c[2*n-1-i];
		d[i].first *= -1;
	}
	c[2*n] = d[2*n] = pi(1e9 + 5, 1e9 + 5);
	seg[0].init(c, 2*n+1);
	seg[1].init(d, 2*n+1);
	int q; scanf("%d",&q);
	while(q--){
		int x, y, dx, dy;
		scanf("%d %d %d %d",&x,&y,&dx,&dy);
		if(dx == 0){
			int pos = lower_bound(c, c+2*n, pi(x, -1)) - c;
			if(pos % 2 == 0 && c[pos].first != x){
				puts("0");
			}
			else{
				printf("%d\n", a[pos/2].idx);
			}
			continue;
		}
		else if(dx < 0){
			printf("%d\n", query(b, d, 1, -x, y, -dx, dy));
		}
		else{
			printf("%d\n", query(a, c, 0, x, y, dx, dy));
		}
	}
}

g.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

char s[1005][1005];
bool vis[1005][1005];
int n, m;

int dfs(int x, int y){
	if(vis[x][y]) return 0;
	vis[x][y] = 1;
	if(x == n-1) return 1;
	for(int i=0; i<4; i++){
		if(x + dx[i] >= n || x + dx[i] < 0 || y + dy[i] >= m || y + dy[i] < 0 || 
				s[x+dx[i]][y+dy[i]] == '1') continue;
		if(dfs(x + dx[i], y + dy[i])){
			return 1;
		}
	}
	return 0;
}

int main(){
	cin >> n >> m;
	for(int i=0; i<n; i++) cin >> s[i];
	for(int i=0; i<m; i++){
		if(s[0][i] == '0' && dfs(0, i)){
			puts("YES");
			return 0;
		}
	}
	puts("NO");
}

i.cpp

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int m, n;

int main(){
	cin >> m >> n;
	int px = 0, py = 0;
	int d = 0;
	while(n--){
		string w;
		int x;
		cin >> w >> x;
		if(w == "MOVE"){
			px += x * dx[d];
			py += x * dy[d];
			if(max(px, py) > m || min(px, py) < 0){
				cout << -1;
				return 0;
			}
		}
		else{
			if(x == 0){
				d = (d+1) % 4;
			}
			else{
				d = (d+3) % 4;
			}
		}
	}
	cout << px << " " << py;
}

j.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

struct pnt{
	int x, y, v;
	bool operator<(const pnt &p)const{
		return pi(x, y) < pi(p.x, p.y);
	}
	bool operator==(const pnt &p)const{
		return x == p.x && y == p.y && v == p.v;
	}
	bool operator!=(const pnt &p)const{
		return !(*this == p);
	}
}a[500005];

void ensure(bool p){
	if(!p){
		puts("-1");
		exit(0);
	}
}

lint solve(pnt a, pnt b){
	return abs(a.x - b.x) + abs(a.y - b.y);
}

int n;

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].v);
	}
	sort(a, a+n);
	lint ret = 0;
	for(int t=0; t<2; t++){
		pnt nul = {0, 0, -1};
		pnt lo = nul, hi = nul;
		for(int i=0; i<n; i++){
			if(i == 0){
				ensure(a[i].v == 1);
				continue;
			}
			if(i == n-1){
				ensure(lo != nul && hi != nul);
				ensure(lo.y < a[i].y && a[i].y < hi.y);
				ret += solve(a[i], lo) + solve(a[i], hi);
				break;
			}
			if(a[i].v == 0){
				ensure(lo == nul || hi == nul);
				if(lo == nul) lo = a[i];
				else hi = a[i];
				if(hi.y < lo.y) swap(lo, hi);
			}
			else{
				ensure(lo != nul || hi != nul);
				if(lo == nul){
					ensure(a[i].y != hi.y);
					ret += solve(a[i], hi);
					hi = nul;
					continue;
				}
				if(hi == nul){
					ensure(a[i].y != lo.y);
					ret += solve(a[i], lo);
					lo = nul;
					continue;
				}
				if(a[i].y > hi.y){
					ret += solve(a[i], hi);
					hi = nul;
				}
				else if(a[i].y < lo.y){
					ret += solve(a[i], lo);
					lo = nul;
				}
				else if(lo.y < a[i].y && a[i].y < hi.y){
					if(a[i+1].v == 1){
						if(a[i+1].y < a[i].y){
							ret += solve(a[i+1], lo) + solve(a[i], hi);
							lo = hi = nul;
						}
						else if(a[i+1].y > a[i].y){
							ret += solve(a[i], lo) + solve(a[i+1], hi);
							lo = hi = nul;
						}
						else ensure(0);
					}
					else{
						if(a[i+1].y > a[i].y){
							ensure(a[i+1].y < hi.y);
							ret += solve(a[i], lo);
							lo = a[i+1];
						}
						else if(a[i+1].y < a[i].y){
							ensure(a[i+1].y > lo.y);
							ret += solve(a[i], hi);
							hi = a[i+1];
						}
						else ensure(0);
					}
					i++;
				}
				else ensure(0);
			}
		}
		reverse(a, a+n);
	}
	cout << ret;
}

k.cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long lint;

const int MAXN = 444;
struct maxflow{
	struct edg{int pos, cap, rev;};
	vector<edg> gph[MAXN];

	void clear(){
		for(int i=0; i<MAXN; i++){
			gph[i].clear();
		}
	}

	void add_edge(int s, int e, int x){
		gph[s].push_back({e, x, (int)gph[e].size()});
		gph[e].push_back({s, 0, (int)gph[s].size()-1});
	}

	int dis[MAXN], pnt[MAXN];

	bool bfs(int src, int sink){
		memset(dis, 0, sizeof(dis));
		memset(pnt, 0, sizeof(pnt));
		queue<int> que;
		que.push(src);
		dis[src] = 1;
		while(!que.empty()){
			int x = que.front();
			que.pop();
			for(int i=0; i<gph[x].size(); i++){
				edg e = gph[x][i];
				if(e.cap > 0 && !dis[e.pos]){
					dis[e.pos] = dis[x] + 1;
					que.push(e.pos);
				}
			}
		}
		return dis[sink] > 0;
	}

	int dfs(int x, int sink, int f){
		if(x == sink) return f;
		for(; pnt[x] < gph[x].size(); pnt[x]++){
			edg e = gph[x][pnt[x]];
			if(e.cap > 0 && dis[e.pos] == dis[x] + 1){
				int w = dfs(e.pos, sink, min(f, e.cap));
				if(w){
					gph[x][pnt[x]].cap -= w;
					gph[e.pos][e.rev].cap += w;
					return w;
				}
			}
		}
		return 0;
	}

	lint match(int src, int sink){
		lint ret = 0;
		while(bfs(src, sink)){
			int r;
			while((r = dfs(src, sink, 2e9))) ret += r;
		}
		return ret;
	}
};

struct circ{
	maxflow mf;
	lint lsum;
	void clear(){
		lsum = 0;
		mf.clear();
	}
	void add_edge(int s, int e, int l, int r){
		lsum += l;
		mf.add_edge(s + 2, e + 2, r - l);
		mf.add_edge(0, e + 2, l);
		mf.add_edge(s + 2, 1, l);
	}
	bool solve(int s, int e){
		mf.add_edge(e+2, s+2, 1e9);
		return lsum == mf.match(0, 1);
	}
	int get(int s, int e){
		s += 2;
		e += 2;
		for(auto &j : mf.gph[s]){
			if(j.pos == e) return j.cap;
		}
		assert(0);
	}
}circ;

int n, m;
int a[205][205], s1[205], s2[205];

void in(int &x){
	double y;
	scanf("%lf",&y);
	x = (int)round(10 * y);
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			in(a[i][j]);
		}
		in(s1[i]);
	}
	for(int i=1; i<=m; i++) in(s2[i]);
	int ls = 0;
	circ.clear();
	for(int i=1; i<=n; i++){
		circ.add_edge(0, i, s1[i] / 10, (s1[i] + 9) / 10);
	}
	for(int i=1; i<=m; i++){
		circ.add_edge(i + n, n + m + 1, s2[i] / 10, (s2[i] + 9) / 10);
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			circ.add_edge(i, j + n, a[i][j] / 10, (a[i][j] + 9) / 10);
		}
	}
	assert(circ.solve(0, n+m+1));
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			printf("%d ", (a[i][j] + 9) / 10 - circ.get(i, j + n));
		}
		printf("%d\n", (s1[i] + 9) / 10 - circ.get(0, i));
	}
	for(int i=1; i<=m; i++){
		printf("%d ", (s2[i] + 9) / 10 - circ.get(i+n, n+m+1));
	}
}

l.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int L[1050000], R[1050000];

int dfs(int v){
	if (v == 0) return 0;
	return min(dfs(L[v]), dfs(R[v])) + 1;
}

int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%d %d", &L[i], &R[i]);
	}
	printf("%d", dfs(1));
}

prelim_a.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int dep[2222222], n;
int mx[2222222];

int main(){
	scanf("%d",&n);
	for(int i=2; i<(2<<n); i++){
		scanf("%d",&dep[i]);
	}
	lint ret = 0;
	for(int i=(1<<n)-1; i; i--){
		mx[i] = max(mx[2*i] + dep[2*i], mx[2*i+1] + dep[2*i+1]);
		ret += 2 * mx[i] - mx[2*i] - mx[2*i+1];
	}
	printf("%lld\n", ret);
}

prelim_b.cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int MAXN = 5005;

int n;
pi a[MAXN];
int pfx[MAXN], sfx[MAXN];

int dist(pi a, pi b){
	int x = b.first - a.first, y = b.second - a.second;
	return x * x + y * y;
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++) scanf("%d %d",&a[i].first,&a[i].second);
	int st = 0, cur = -1;
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			int nxt = dist(a[i], a[j]);
			if(nxt > cur){
				cur = nxt;
				st = i;
			}
		}
	}
	swap(a[0], a[st]);
	sort(a + 1, a + n, [&](const pi &p, const pi &q){
		return dist(a[0], p) < dist(a[0], q);
	});
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++) pfx[i] = max(pfx[i], dist(a[i], a[j]));
		for(int j=i+1; j<n; j++) sfx[i] = max(sfx[i], dist(a[i], a[j]));
	}
	for(int i=1; i<n; i++){
		pfx[i] = max(pfx[i], pfx[i-1]);
		sfx[n-1-i] = max(sfx[n-1-i], sfx[n-i]);
	}
	double ans = 1e9;
	for(int i=0; i<n-1; i++) ans = min(ans, sqrt(pfx[i]) + sqrt(sfx[i + 1]));
	printf("%.10f\n", ans);
}

prelim_c.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

lint segment_distance(pair<pi, pi> a, pair<pi, pi> b){
	pi s1 = a.first, e1 = a.second, s2 = b.first, e2 = b.second;
	if (s1.second == e1.second){
		swap(s1.first, s1.second);
		swap(e1.first, e1.second);
		swap(s2.first, s2.second);
		swap(e2.first, e2.second);
	}
	if (s1 > e1) swap(s1, e1);
	if (s2 > e2) swap(s2, e2);
	if (s2.first == e2.first){
		int dx = abs(s2.first - s1.first);
		int dy = 0;
		if (max(s1.second, s2.second) <= min(e1.second, e2.second)){
			dy = 0;
		}
		else{
			dy = min(abs(e1.second - s2.second), abs(e2.second - s1.second));
		}
		return dx * dx + dy * dy;
	}
	else{
		int dx = 0, dy = 0;
		if (s1.second <= s2.second && s2.second <= e1.second){
			dy = min(abs(s2.first - s1.first), abs(e2.first - s1.first));
			return dy * dy;
		}
		if (s2.first <= s1.first && s1.first <= e2.first){
			dy = min(abs(s2.second - s1.second), abs(s2.second - e1.second));
			return dy * dy;
		}
		dx = min({ abs(s1.first - s2.first), abs(s1.first - e2.first), abs(e1.first - s2.first), abs(e1.first - e2.first) });
		dy = min({ abs(s1.second - s2.second), abs(s1.second - e2.second), abs(e1.second - s2.second), abs(e1.second - e2.second)});
		return dx * dx + dy * dy;
	}
}

int a, b, c, l;
pi pnt[10005];

vector<pair<pi, pi>> sega, segb, segc;
lint dist[10005];
bool vis[10005];

int main(){
	scanf("%*d %*d %d %d %d %d", &a, &b, &c, &l);
	for (int i = 0; i < a; i++){
		scanf("%d %d", &pnt[i].first, &pnt[i].second);
		if (i > 0) sega.emplace_back(pnt[i - 1], pnt[i]);
	}
	for (int i = 0; i < b; i++){
		scanf("%d %d", &pnt[i].first, &pnt[i].second);
		if (i > 0) segb.emplace_back(pnt[i - 1], pnt[i]);
	}
	for (int i = 0; i < c; i++){
		pi a, b;
		scanf("%d %d %d %d", &a.first, &a.second, &b.first, &b.second);
		segc.emplace_back(a, b);
	}
	lint ret = 1e18;
	for (auto &i : sega){
		for (auto &j : segb){
			ret = min(ret, segment_distance(i, j));
		}
	}
	if (ret > l){
		ret = 1e18;
	}
	memset(dist, 0x3f, sizeof(dist));
	for (auto &i : sega){
		for (int j = 0; j < segc.size(); j++){
			lint k = segment_distance(i, segc[j]);
			if (k <= l){
				dist[j] = min(dist[j], k);
			}
		}
	}
	for (int i = 0; i < segc.size(); i++){
		lint cur = 1e18, pos = -1;
		for (int j = 0; j < segc.size(); j++){
			if (!vis[j] && dist[j] < cur){
				cur = dist[j];
				pos = j;
			}
		}
		if (pos == -1) break;
		vis[pos] = 1;
		for (auto &j : segb){
			lint w = segment_distance(segc[pos], j);
			if (w <= l) ret = min(ret, w + dist[pos]);
		}
		for (int j = 0; j < segc.size(); j++){
			lint w = segment_distance(segc[pos], segc[j]);
			if (w <= l && j != pos)
				dist[j] = min(dist[j], dist[pos] + w);
		}
	}
	if (ret > 1e16){
		ret = -1;
	}
	printf("%lld", ret);
}

prelim_d.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, d;
const int mod = 31991;

struct mat{
	int adj[55][55];
	mat operator*(const mat &m)const{
		mat ret;
		for(int i=0; i<d; i++){
			for(int j=0; j<d; j++){
				ret.adj[i][j] = 0;
				for(int k=0; k<d; k++){
					ret.adj[i][j] += adj[i][k] * m.adj[k][j];
					ret.adj[i][j] %= mod;
				}
			}
		}
		return ret;
	}
}ret, piv;

int main(){
	cin >> d >> n;
	for(int i=0; i<d; i++){
		ret.adj[i][i] = 1;
		piv.adj[0][i] = 1;
	}
	for(int i=1; i<d; i++){
		piv.adj[i][i-1] = 1;
	}
	while(n){
		if(n&1) ret = ret * piv;
		piv = piv * piv;
		n >>= 1;
	}
	cout << ret.adj[0][0];
}

prelim_e.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 100005;

lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

pi cur;

struct seg{
	pi s, e;
	int idx;
	double func(){
		int a = e.second - s.second;
		int b = s.first - e.first;
		lint c = 1ll * a * s.first + 1ll * b * s.second;
		return c / (a * (1.0 * cur.first / cur.second) + b);
	}
};

struct event{
	pi p;
	int x, y;
	bool operator<(const event &ev)const{
		return ccw(pi(0, 0), p, ev.p) > 0;
	}
};

vector<pi> v[MAXN];
vector<event> ev;
int chk[MAXN];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		int k;
		scanf("%d",&k);
		v[i].resize(k);
		for(auto &j : v[i]) scanf("%d %d",&j.first,&j.second);
		auto cmp = [&](const pi &a, const pi &b){
			return ccw(pi(0, 0), a, b) > 0;
		};
		rotate(v[i].begin(), max_element(v[i].begin(), v[i].end(), cmp), v[i].end());
		int m = min_element(v[i].begin(), v[i].end(), cmp) - v[i].begin();
		v[i].resize(m + 1);
		reverse(v[i].begin(), v[i].end());
		for(int j=0; j<v[i].size(); j++){
			ev.push_back({v[i][j], i, j});
		}
	}
	sort(ev.begin(), ev.end());
	auto cmp = [](seg a, seg b){
		return a.func() < b.func();
	};
	set<seg, decltype(cmp)> s(cmp);
	for(int ii=0; ii + 1<ev.size(); ii++){
		event i = ev[ii], j = ev[ii + 1];
		if(i.y != 0){
			seg t = (seg){v[i.x][i.y-1], v[i.x][i.y], i.x};
			auto x = s.lower_bound(t);
			if(x != s.end() && x->idx == i.x) s.erase(x);
			else s.erase(--x);
		}
		cur = pi(i.p.first + j.p.first, i.p.second + j.p.second);
		if(i.y != v[i.x].size() - 1){
			s.insert({v[i.x][i.y], v[i.x][i.y + 1], i.x});
		}
		if(!s.empty()) chk[s.begin()->idx] = 1;
	}
	cout << count(chk + 1, chk + n + 1, 0);
}

prelim_f.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

int n, a, b, d2[10005];
short dp[10005][10005];
char str[10005];

bool ok(int s, int e){
	int m = dp[s][e];
	return 2 * m * b >= a * (e-s+1);
}
int main(){
	cin >> n >> a >> b >> str;
	for(int i=1; i<n; i++){
		for(int j=0; j+i<n; j++){
			if(str[j] == str[j+i]) dp[j][j+i] = dp[j+1][j+i-1] + 1;
		}
	}
	for(int i=1; i<=n; i++){
		d2[i] = 1e9;
		for(int j=0; j<i; j++){
			if(ok(j, i-1)) d2[i] = min(d2[i], d2[j] + 1);
		}
	}
	if(d2[n] > 1e8) d2[n] = 0;
	cout << d2[n];
}

prelim_g.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 5005;

vector<int> gph[MAXN];
set<pi> s;

void dfs(int x, int y){
	if(s.find(pi(x, y)) != s.end()) return;
	s.insert(pi(x, y));
	int l = find(gph[y].begin(), gph[y].end(), x) - gph[y].begin() + 1;
	l %= gph[y].size();
	dfs(y, gph[y][l]);
}

int solve2(){
	int n;
	scanf("%d",&n);
	int edg = 0;
	for(int i=1; i<=n; i++){
		int x;
		scanf("%d",&x);
		gph[i].resize(x);
		for(auto &j : gph[i]) scanf("%d",&j);
		edg += x;
	}
	edg /= 2;
	if(edg > 20000) return -1;
	int ans = 0;
	for(int i=1; i<=n; i++){
		for(int j=0; j<gph[i].size(); j++){
			if(s.find(pi(i, gph[i][j])) == s.end()){
				dfs(i, gph[i][j]);
				ans++;
			}
		}
	}
	return n - edg + ans == 2 ? 1 : -1;
}


void add_edge(int s, int e){
	gph[s].push_back(e);
	gph[e].push_back(s);
}

bool has_edge(int s, int e){
	return find(gph[s].begin(), gph[s].end(), e) != gph[s].end();
}

void del_edge(int s, int e){
	gph[s].erase(find(gph[s].begin(), gph[s].end(), e));
	gph[e].erase(find(gph[e].begin(), gph[e].end(), s));
}

int solve1(){
	int n, m;
	scanf("%d %*d %d",&n,&m);
	for(int i=0; i<m; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		add_edge(s, e);
	}
	queue<int> que;
	for(int i=1; i<=n; i++){
		if(gph[i].size() == 2){
			que.push(i);
		}
	}
	while(!que.empty()){
		int x = que.front();
		que.pop();
		if(gph[x].size() != 2) continue;
		int l = gph[x][0];
		int r = gph[x][1];
		if(l == r) return -1;
		del_edge(l, x);
		del_edge(r, x);
		add_edge(l, r);
		if(gph[l].size() == 2) que.push(l);
		if(gph[r].size() == 2) que.push(r);
	}
	vector<int> vtx;
	for(int i=1; i<=n; i++){
		if(gph[i].size()) vtx.push_back(i);
	}
	if(vtx.size() == 5){
		for(auto &i : vtx){
			if(gph[i].size() != 4) return -1;
		}
		for(int i=0; i<vtx.size(); i++){
			for(int j=0; j<i; j++){
				if(!has_edge(vtx[i], vtx[j])) return -1;
			}
		}
		return 1;
	}
	if(vtx.size() == 6){
		for(auto &i : vtx){
			if(gph[i].size() != 3) return -1;
		}
		sort(vtx.begin(), vtx.end());
		int ans = -1;
		do{
			bool ok = 1;
			for(int i=0; i<3; i++){
				for(int j=3; j<6; j++){
					if(!has_edge(vtx[i], vtx[j])) ok = 0;
				}
			}
			if(ok) ans = 1;
		}while(next_permutation(vtx.begin(), vtx.end()));
		return ans;
	}
	return -1;
}

int main(){
	int q;
	scanf("%d",&q);
	if(q == -1) printf("%d\n", solve1());
	else printf("%d\n", solve2());
}

prelim_h.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, lint> pi;
const int MAXN = 3005;

struct maxflow{
	struct edg{int pos, cap, rev;};
	vector<edg> gph[MAXN];
	void clear(){for(int i=0; i<MAXN; i++) gph[i].clear();}
	void add_edge(int s, int e, int x){
		gph[s].push_back({e, x, (int)gph[e].size()});
		gph[e].push_back({s, 0, (int)gph[s].size()-1});
	}
	int dis[MAXN], pnt[MAXN];
	bool bfs(int src, int sink){
		memset(dis, 0, sizeof(dis));
		memset(pnt, 0, sizeof(pnt));
		queue<int> que;
		que.push(src);
		dis[src] = 1;
		while(!que.empty()){
			int x = que.front();
			que.pop();
			for(auto &e : gph[x]){
				if(e.cap > 0 && !dis[e.pos]){
					dis[e.pos] = dis[x] + 1;
					que.push(e.pos);
				}
			}
		}
		return dis[sink] > 0;
	}
	int dfs(int x, int sink, int f){
		if(x == sink) return f;
		for(; pnt[x] < gph[x].size(); pnt[x]++){
			edg e = gph[x][pnt[x]];
			if(e.cap > 0 && dis[e.pos] == dis[x] + 1){
				int w = dfs(e.pos, sink, min(f, e.cap));
				if(w){
					gph[x][pnt[x]].cap -= w;
					gph[e.pos][e.rev].cap += w;
					return w;
				}
			}
		}
		return 0;
	}
	lint match(int src, int sink){
		lint ret = 0;
		while(bfs(src, sink)){
			int r;
			while((r = dfs(src, sink, 2e9))) ret += r;
		}
		return ret;
	}
}mf;


struct circ{
	maxflow mf;
	lint lsum;
	void clear(){
		lsum = 0;
		mf.clear();
	}
	void add_edge(int s, int e, int l, int r){
		lsum += l;
		mf.add_edge(s + 2, e + 2, r - l);
		mf.add_edge(0, e + 2, l);
		mf.add_edge(s + 2, 1, l);
	}
	bool solve(int s, int e){
		mf.add_edge(e+2, s+2, 1e9); // to reduce as maxflow with lower bounds, in circulation problem skip this line
		return lsum == mf.match(0, 1);
		// to get maximum LR flow, run maxflow from s+2 to e+2 again
	}
}circ;

int n, m, s, e;
pi vp[105];
vector<int> idx[105];
vector<pi> itv[105];

int main(){
	cin >> n >> m >> s >> e;
	tie(s, e) = pi(m-e, m-s);
	for(int i=0; i<m; i++){
		int s, e;
		cin >> s >> e;
		vp[i] = pi(n-e, n-s);
	}
	int ptr = n;
	for(int i=0; i<n; i++){
		int k;
		cin >> k;
		idx[i].resize(k);
		itv[i].resize(k);
		circ.add_edge(0, i+1, s, e);
		for(int j=0; j<k; j++){
			int s, e, d;
			cin >> d >> s >> e;
			idx[i][j] = ++ptr;
			itv[i][j] = pi(s, e);
			circ.add_edge(i+1, idx[i][j], d, e - s + 1);
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<itv[i].size(); j++){
			for(int k=itv[i][j].first; k<=itv[i][j].second; k++){
				circ.add_edge(idx[i][j], ptr + k, 0, 1);
			}
		}
	}
	for(int i=0; i<m; i++){
		circ.add_edge(ptr + i + 1, ptr + m + 1, vp[i].first, vp[i].second);
	}
	if(!circ.solve(0, ptr + m + 1)){
		puts("-1");
		return 0;
	}
	puts("1");
	for(int i=0; i<n; i++){
		vector<int> v;
		for(auto &j : idx[i]){
			for(auto &k : circ.mf.gph[j+2]){
				if(k.pos > ptr+2 && k.cap == 0){
					v.push_back(k.pos - ptr - 2);
				}
			}
		}
		sort(v.begin(), v.end());
		printf("%d ", v.size());
		for(auto &i : v) printf("%d ", i);
		puts("");
	}
}

prelim_i.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, lint> pi;

int n, a[1005];

int main(){
	cin >> n;
	for(int i=0; i<n; i++) cin >> a[i];
	sort(a, a+n);
	for(int i=0; i<=n; i++){
		bool ok1 = 0, ok2 = 0;
		if(i == 0 || a[n-i] >= i) ok1 = 1;
		if(i == n || a[n-i-1] <= i) ok2 = 1;
		if(ok1 && ok2){
			printf("%d ", i);
		}
	}
}

prelim_j.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, s[100005], e[100005], l;
map<int, int> mp;

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&s[i],&e[i]);
		if(s[i] > e[i]) swap(s[i], e[i]);
	}
	scanf("%d",&l);
	for(int i=0; i<n; i++){
		if(e[i] - s[i] > l) continue;
		tie(s[i], e[i]) = pi(e[i] - l, s[i]);
		mp[2*s[i]]++;
		mp[2*e[i]+1]--;
	}
	int dap = 0, ret = 0;
	for(auto &i : mp){
		ret += i.second;
		dap = max(dap, ret);
	}
	cout << dap;
}

prelim_l.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, lint> pi;

int n, w, l, a[1005];
int dp[1005];

int main(){
	cin >> n >> w >> l;
	for(int i=1; i<=n; i++) cin >> a[i];
	deque<int> dq;
	for(int i=0; i<w; i++) dq.push_back(0);
	int sum = 0, ret = 0, pnt = 1;
	while(pnt <= n){
		sum -= dq.front();
		dq.pop_front();
		if(a[pnt] + sum <= l){
			dq.push_back(a[pnt]);
			sum += a[pnt];
			pnt++;
		}
		else{
			dq.push_back(0);
		}
		ret++;
	}
	cout << ret + w;
}