oj.uz

Submission #63230

# Submission time Handle Problem Language Result Execution time Memory
63230 2018-08-01T06:36:10 Z 윤교준(#1834) Alternating Current (BOI18_alternating) C++11
0 / 100
 3000 ms 13688 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fuk() { puts("impossible"); exit(0); }

const bool debug = 0;
const int MAXN = 100005;
const int MAXM = 100005;

struct PFS {
	int d[MAXN*2], N;
	void init() { fill(d, d+MAXN*2, 0); }
	void add(int s, int e) { d[s]++; d[e+1]--; }
	bool cal() {
		for(int i = 1; i <= N*2; i++) d[i+1] += d[i];
		for(int i = 1; i <= N; i++)
			if(!d[i] && !d[i+N]) return false;
		return true;
	}
} preA, preB;

vector<int> T[MAXN*2];
vector<int> G[MAXM], CH;

int ud[MAXM];
int A[MAXM], B[MAXM];

int Ans[MAXM];
int N, M;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

bool isValid() {
	preA.init(); preB.init();
	for(int i = 1; i <= M; i++)
		(Ans[i] ? preA : preB).add(A[i], B[i]);
	return preA.cal() && preB.cal();
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	preA.N = preB.N = N;
	for(int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i];
		if(A[i]-1 == B[i]) { A[i] = 1; B[i] = N; }
		if(A[i] > B[i]) B[i] += N;
		T[A[i]].eb(i);
		T[A[i]+N].eb(i);

		if(debug) printf("%d ; %d %d\n", i, A[i], B[i]);
	}

	iota(ud, ud+MAXM, 0);
	{
		int ci = -1;
		for(int i = 1; i <= M; i++)
			if(1 == A[i] && B[i] == N)
				ci = i;
		if(0 < ci) {
			for(int i = 1; i <= M; i++)
				uf(ci, i);
		} else {
			for(int i = 1; i <= M; i++) for(int j = 1; j <= M; j++) {
				if(A[i] <= A[j] && B[j] <= B[i]) uf(i, j);
				else if(A[i]+N <= A[j] && B[j] <= B[i]+N) uf(i, j);
				else if(A[i] <= A[j]+N && B[j]+N <= B[i]) uf(i, j);
			}
			/*
			for(int i = 1, st = 0, et = 0, ei = -1; i <= N*2; i++) {
				for(int v : T[i]) {
					int e = i + (B[v]-A[v]);
					if(e <= et) uf(ei, v);
					else {
						if(st == i) uf(v, ei);
						st = i; et = e; ei = v;
					}
				}
			}
			*/
		}
	}
	for(int i = 1; i <= M; i++) (uf(i) == i ? CH : G[uf(i)]).eb(i);
	sort(allv(CH), [&](int a, int b) { return A[a] < A[b]; });

	if(debug) {
		for(int i = 1; i <= M; i++) printf("%d ; %d\n", i, uf(i));
		for(int v : CH) printf("%d\n", v);
	}

	for(int v : CH) preA.add(A[v], B[v]);
	if(!preA.cal()) fuk();
	preA.init();

	if(sz(CH) & 1) {
		for(int i = 0, n = sz(CH); i < n; i++) {
			for(int j = 0; j < i; j++) Ans[CH[j]] = (i-j-1) & 1;
			for(int j = i; j < n; j++) Ans[CH[j]] = (j-i) & 1;
			for(int j = 1; j <= M; j++) if(uf(j) != j)
				Ans[j] = !Ans[uf(j)];
			if(isValid()) break;
		}
	} else {
		for(int i = 0, n = sz(CH); i < n; i++)
			Ans[CH[i]] = i & 1;
		for(int i = 1; i <= M; i++) if(uf(i) != i)
			Ans[i] = !Ans[uf(i)];
	}

	if(!isValid()) fuk();
	for(int i = 1; i <= M; i++) printf("%d", !!Ans[i]);
	puts("");
	return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9336 KB Output is correct
2 Correct 15 ms 9444 KB Output is correct
3 Correct 14 ms 9444 KB Output is correct
4 Correct 14 ms 9444 KB Output is correct
5 Correct 12 ms 9504 KB Output is correct
6 Incorrect 13 ms 9632 KB 'impossible' claimed, but there is a solution
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9336 KB Output is correct
2 Correct 15 ms 9444 KB Output is correct
3 Correct 14 ms 9444 KB Output is correct
4 Correct 14 ms 9444 KB Output is correct
5 Correct 12 ms 9504 KB Output is correct
6 Incorrect 13 ms 9632 KB 'impossible' claimed, but there is a solution
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9336 KB Output is correct
2 Correct 15 ms 9444 KB Output is correct
3 Correct 14 ms 9444 KB Output is correct
4 Correct 14 ms 9444 KB Output is correct
5 Correct 12 ms 9504 KB Output is correct
6 Incorrect 13 ms 9632 KB 'impossible' claimed, but there is a solution
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 12252 KB Output is correct
2 Correct 14 ms 12252 KB Output is correct
3 Correct 39 ms 13688 KB Output is correct
4 Correct 38 ms 13688 KB Output is correct
5 Execution timed out 3029 ms 13688 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9336 KB Output is correct
2 Correct 15 ms 9444 KB Output is correct
3 Correct 14 ms 9444 KB Output is correct
4 Correct 14 ms 9444 KB Output is correct
5 Correct 12 ms 9504 KB Output is correct
6 Incorrect 13 ms 9632 KB 'impossible' claimed, but there is a solution
7 Halted 0 ms 0 KB -