oj.uz

Submission #139815

# Submission time Handle Problem Language Result Execution time Memory
139815 2019-08-01T13:15:53 Z emaborevkovic Alternating Current (BOI18_alternating) C++14
0 / 100
 57 ms 5232 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#include <vector>

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define _ << " " << 
#define trace(x) cerr << #x << " " << x << endl
#define ll long long

const int N = 1e5 + 11;
int n, m, unutra[N];
pair <int, int> f1[N], f2[N];
pair <int, int> a1[N];
pair <pair <int, int> , pair <int,int> > izb[N];
vector <pair <pair <int, int>, int> > v;
int ak[N], sv[N], res[N], brojac = 0;

void ubaci1 (int x, int koliko, int ind) {
	for (; x <= n; x+=x&-x) {
		f1[x] = max(f1[x], mp(koliko, ind));
	}
}

pair <int, int> upit1 (int x) {
	pair <int, int> ret = mp(0, 0);
	for (; x > 0; x-=x&-x) {
		ret = max(ret, f1[x]);
	}
	return ret;
}

void ubaci2 (int x, int koliko, int ind) {
	for (; x <= n; x+=x&-x) {
		f2[x] = max(f2[x], mp(koliko, ind));
	}
}

pair <int, int> upit2 (int x) {
	pair <int, int> ret = mp(0, 0);
	for (; x > 0; x-=x&-x) {
		ret = max(ret, f2[x]);
	}
	return ret;
}

bool sijeku (int x, int y) {
	int a = v[x].ff.ff, b = v[x].ff.ss;
	int c = v[y].ff.ff, d = v[y].ff.ss;
	if (a <= b && c <= d) {
		if (c >= a && c <= b+1) return 1;
		if (a >= c && a <= d+1) return 1;
		if (a == 1 && d == n) return 1;
		if (c == 1 && b == n) return 1;
	}
	if (a > b && c > d) {
		return 1;
	} 
	if (a > b) {
		if (c <= b+1) return 1;
		if (d >= a-1) return 1;
		return 0;
	}
	if (b >= c-1) return 1;
	if (a <= d+1) return 1;
	return 0;
}

bool popl (int x, int y, int z) {
	int poc = v[x].ff.ss, kraj = v[z].ff.ff;
	if (!sijeku(x, y)) return 1;
	if (!sijeku(y, z)) return 1;
	if (v[y].ff.ff > v[y].ff.ss) {
		if (v[x].ff.ff > v[x].ff.ss && poc >= kraj-1) return 0;
		if (v[z].ff.ff > v[z].ff.ss && poc >= kraj-1) return 0;	
		if (v[z].ff.ff > v[z].ff.ss && v[x].ff.ff > v[x].ff.ss) return 0;
		if (kraj == n && poc == 1) return 0;
	}
	else if (poc >= kraj-1 && poc != n && kraj != 1) return 0;
	if (v[y].ff.ff > v[y].ff.ss && v[x].ff.ff <= v[x].ff.ss && v[z].ff.ff <= v[z].ff.ss) {
		if (ak[n] - ak[poc] == n-poc && ak[kraj-1] == kraj-1) return 0;
		return 1;
	}
	if (kraj != n && poc != 1) {
		if (ak[kraj-1] - ak[poc] == kraj-1-poc) return 0;
		return 1;
	}
	if (kraj == n) {
		if (ak[kraj-1] == kraj-1) return 0;
		return 1;
	}
	if (poc == 1) {
		if (ak[n] - ak[kraj] == n-kraj) return 0;
	}
	return 1;
}

void tri (int x) {
	int a = v[x].ff.ff, b = v[x].ff.ss;
	if (a > b) {
		if (ak[a-1]-ak[b] < a-1-b) return;
	}
	else {
		if (ak[a-1] < a-1 || ak[n] - ak[b] < n-b) return;
	}
	for (int i=0;i<3;i++) {
		if (i == x) res[v[i].ss] = 1;
		else res[v[i].ss] = 0;
	}
	for (int i=0;i<m;i++) {
		if (unutra[i] > 0) {
			res[i] = !res[unutra[i]-1];
		}
	}
	brojac++;
}

bool poplo (int x, int z, int q, int y) {
	int a = v[x].ff.ff, b = v[x].ff.ss;
	int c = v[y].ff.ff, d = v[y].ff.ss;
	if (v[z].ff.ff > v[z].ff.ss || v[q].ff.ff > v[q].ff.ss || (v[z].ff.ff == n && v[q].ff.ss == 1)) {
		if (a > b && c > d) return 1;
		if (b == n && c == 1) return 1;
		if (a > b) {
			if (c <= b+1) return 1;
			if (ak[c-1] - ak[b] == c-1-b) return 1;
		}
		if (c > d) {
			if (b >= c-1) return 1;
			if (ak[c-1] - ak[b] == c-1-b) return 1;
		}
		if (ak[n] - ak[b] == n-b && ak[c-1] == c-1) return 1;
		return 0;
	}
	if (b == n) {
		if (ak[c-1] == c-1) return 1;
		return 0;
	}
	if (c == 1) {
		if (ak[n] - ak[b] == n-b) return 1;
		return 0;
	}
	if (ak[c-1]-ak[b] == c-1-b) return 1;
	return 0;
}

int main() {
	cin >> n >> m;
	for (int i=0;i<m;i++) {
		scanf("%d%d", &a1[i].ff, &a1[i].ss);
		izb[i].ff.ff = a1[i].ss-a1[i].ff+1;
		if (izb[i].ff.ff <= 0) izb[i].ff.ff = a1[i].ss+n-a1[i].ff+1;
		izb[i].ff.ss = i;
		izb[i].ss.ff = a1[i].ff;
		izb[i].ss.ss = a1[i].ss;
	}
	sort (izb, izb + m);
	for (int i=m-1;i>=0;i--) {
		if (izb[i].ss.ff > izb[i].ss.ss) {
			pair <int, int> sada = upit2(izb[i].ss.ff); 
			if (sada.ff >= izb[i].ss.ss) {
				sv[1]++;
				sv[izb[i].ss.ss+1]--;
				sv[izb[i].ss.ff]++;
				unutra[izb[i].ff.ss] = sada.ss+1;
			}
			else v.pb(mp(izb[i].ss, izb[i].ff.ss));
			ubaci2(izb[i].ss.ff, izb[i].ss.ss, izb[i].ff.ss);
			ubaci1(1, izb[i].ss.ss, izb[i].ff.ss);
			ubaci1(izb[i].ss.ff, n, izb[i].ff.ss);
		}
		else {
			pair <int, int> sada = upit1(izb[i].ss.ff);
			if (sada.ff >= izb[i].ss.ss) {
				sv[izb[i].ss.ff]++;
				sv[izb[i].ss.ss+1]--;
				unutra[izb[i].ff.ss] = sada.ss+1;
			}
			else v.pb(mp(izb[i].ss, izb[i].ff.ss));
			ubaci1(izb[i].ss.ff, izb[i].ss.ss, izb[i].ff.ss);
		}
	}
	for (int i=1;i<=n;i++) {
		sv[i] += sv[i-1];
		if (sv[i] > 0) ak[i]=1+ak[i-1];
		else ak[i]=ak[i-1];
	} 
	sort(v.begin(), v.end());
	int br = 0;
	int siz = v.size();
	if (siz == 1) {
		int a = v[0].ff.ff, b = v[0].ff.ss;
		for (int i=1;i<=n;i++) {
			if (sv[i] == 0) {
				cout << "impossible";
				return 0;
			}
		}
		if ((a == 1 && b == n) || a == b+1) {
			res[v[0].ss]=1;
			for (int i=0;i<m;i++) printf("%d", res[i]);
			return 0;
		}
		cout << "impossible";
		return 0;
	}
	if (siz == 2) {
		int a = v[0].ff.ff, b = v[0].ff.ss;
		int c = v[1].ff.ff, d = v[1].ff.ss;
		int dva[N];
		memset(dva, 0, sizeof dva);
		if (a <= b) {
			for (int i=a;i<=b;i++) dva[i]++;
		}
		else {
			for (int i=a;i<=n;i++) dva[i]++;
			for (int i=1;i<=b;i++) dva[i]++;
		}
		if (c <= d) {
			for (int i=c;i<=d;i++) dva[i]++;
		}
		else {
			for (int i=c;i<=n;i++) dva[i]++;
			for (int i=1;i<=d;i++) dva[i]++;
		}
		for (int i=1;i<=n;i++) {
			if (dva[i] == 0) {
				cout << "impossible";
				return 0;
			}
			if (dva[i] == 1 && sv[i] < 1) {
				cout << "impossible";
				return 0;
			}
		}
		for (int i=0;i<siz;i++) {
			res[v[i].ss] = i%2;
		}
		for (int i=0;i<m;i++) {
			if (unutra[i] > 0) {
				res[i] = !res[unutra[i]-1];
			}
		}
		for (int i=0;i<m;i++) printf("%d", res[i]);
		return 0;
	}
	for (int i=1;i<siz-1;i++) {
		if (popl(i-1, i, i+1)) br++;
	}
	if (popl(siz-1, 0, 1)) br++;
	if (popl(siz-2, siz-1, 0)) br++;
	if (br > 0) {
		cout << "impossible";
		return 0;
	}
	if (siz % 2 == 0) {
		for (int i=0;i<siz;i++) {
			res[v[i].ss] = i%2;
		}
		for (int i=0;i<m;i++) {
			if (unutra[i] > 0) {
				res[i] = !res[unutra[i]-1];
			}
		}
		for (int i=0;i<m;i++) printf("%d", res[i]);
		return 0;
	}
	if (siz == 3) {
		br = 0;
		tri(0);
		tri(1);
		tri(2);
		if (brojac > 0) {
			for (int i=0;i<m;i++) printf("%d", res[i]);
		}
		else cout << "impossible";
		return 0;
	}
	for (int i=0;i<siz-3;i++) {
		if (poplo(i, i+1, i+2, i+3)) {
			res[v[i+1].ss] = 1;
			res[v[i+2].ss] = 1;
			for (int j=i;j>=0;j--) res[v[j].ss] = !res[v[j+1].ss];
			for (int j=i+3;j<siz;j++) res[v[j].ss] = !res[v[j-1].ss];
			for (int j=0;j<m;j++) {
				if (unutra[j] > 0) {
					res[j] = !res[unutra[j]-1];
				}
			}
			for (int j=0;j<m;j++) printf("%d", res[j]);
			return 0;
		}
	}
	if (poplo(siz-3, siz-2, siz-1, 0)) {
		for (int i=1;i<siz;i++) {
			if (i == siz-1) res[v[i].ss] = res[v[i-1].ss];
			else res[v[i].ss] = !res[v[i-1].ss];
		}
	}
	else if (poplo(siz-2, siz-1, 0, 1)) {
		for (int i=1;i<siz;i++) {
			if (i == siz-1) res[v[i].ss] = 0;
			else res[v[i].ss] = !res[v[i-1].ss];
		}
	}
	else if (poplo(siz-1, 0, 1, 2)) {
		for (int i=1;i<siz;i++) {
			if (i == 1) res[v[i].ss] = 0;
			else res[v[i].ss] = !res[v[i-1].ss];
		}
	}
	else {
		cout << "impossible";
		return 0;
	}
	for (int i=0;i<m;i++) {
		if (unutra[i] > 0) {
			res[i] = !res[unutra[i]-1];
		}
	}
	for (int i=0;i<m;i++) printf("%d", res[i]);
	return 0;
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:157:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a1[i].ff, &a1[i].ss);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 788 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 760 KB Output is correct
22 Incorrect 2 ms 376 KB 'impossible' claimed, but there is a solution
23 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 788 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 760 KB Output is correct
22 Incorrect 2 ms 376 KB 'impossible' claimed, but there is a solution
23 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 788 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 760 KB Output is correct
22 Incorrect 2 ms 376 KB 'impossible' claimed, but there is a solution
23 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3960 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 19 ms 2936 KB Output is correct
4 Correct 22 ms 2936 KB Output is correct
5 Incorrect 57 ms 5232 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 788 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 760 KB Output is correct
22 Incorrect 2 ms 376 KB 'impossible' claimed, but there is a solution
23 Halted 0 ms 0 KB -