Submission #106427

# Submission time Handle Problem Language Result Execution time Memory
106427 2019-04-18T11:47:53 Z eriksuenderhauf Alternating Current (BOI18_alternating) C++11
0 / 100
135 ms 14480 KB
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 2e5 + 5;
const double eps = 1e-9;
int a[MAXN], vis[MAXN], cnt = 5;
char ans[MAXN];
vii adj[MAXN];
vi comp;
int n, m;

bool dfs(int u, int p) {
	if (u == p) 
		return 1;
	if (vis[u % n] == cnt)
		return 0;
	vis[u % n] = cnt;
	for (pii nx: adj[u]) {
		comp.pb(nx.se);
		if (dfs(nx.fi, p))
			return 1;
		comp.pop_back();
	}
	return 0;
}

bool ok(int cur) {
	vis[cur] = ++cnt;
	for (pii nx: adj[cur]) {
		if (nx.fi == cur-1) continue;
		comp.pb(nx.se);
		if (dfs(nx.fi, cur + n))
			return 1;
		comp.pop_back();
	}
	return 0;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int l, r;
		scanf("%d %d", &l, &r);
		if (l > r) {
			a[l]++, a[n + 1]--;
			a[1]++, a[r + 1]--;
			l--, r += n;
			adj[l].pb({r, i});
			adj[l+n].pb({2*n, i});
		} else {
			a[l]++, a[r + 1]--;
			l--;
			adj[l].pb({r, i});
			adj[l+n].pb({r+n, i});
		}
		ans[i] = '1';
	}
	for (int i = 1; i <= n; i++) {
		a[i] += a[i - 1];
		if (a[i] == 1)
			return !printf("impossible\n");
	}
	for (int i = 1; i <= n; i++) {
		a[i] = max(0, min(1, a[i] - 2));
		if (!a[i]) continue;
		adj[i].pb({i - 1, -1});
		adj[i + n].pb({i - 1 + n, -1});
	}
	for (int i = 0; i < n; i++) {
		if (!ok(i)) continue;
		for (int j: comp)
			if (j != -1)
				ans[j] = '0';
		return !printf("%s\n", ans);
	}
	return 0;
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
alternating.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4964 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 8 ms 4992 KB Output is correct
11 Correct 7 ms 5068 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 6 ms 4992 KB Output is correct
14 Correct 8 ms 4992 KB Output is correct
15 Correct 8 ms 4992 KB Output is correct
16 Correct 7 ms 4992 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 8 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 7 ms 4992 KB Output is correct
21 Correct 7 ms 4992 KB Output is correct
22 Correct 7 ms 4992 KB Output is correct
23 Correct 6 ms 4992 KB Output is correct
24 Correct 7 ms 4992 KB Output is correct
25 Correct 8 ms 4992 KB Output is correct
26 Correct 7 ms 4992 KB Output is correct
27 Incorrect 7 ms 4992 KB Unexpected end of file - token expected
28 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4964 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 8 ms 4992 KB Output is correct
11 Correct 7 ms 5068 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 6 ms 4992 KB Output is correct
14 Correct 8 ms 4992 KB Output is correct
15 Correct 8 ms 4992 KB Output is correct
16 Correct 7 ms 4992 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 8 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 7 ms 4992 KB Output is correct
21 Correct 7 ms 4992 KB Output is correct
22 Correct 7 ms 4992 KB Output is correct
23 Correct 6 ms 4992 KB Output is correct
24 Correct 7 ms 4992 KB Output is correct
25 Correct 8 ms 4992 KB Output is correct
26 Correct 7 ms 4992 KB Output is correct
27 Incorrect 7 ms 4992 KB Unexpected end of file - token expected
28 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4964 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 8 ms 4992 KB Output is correct
11 Correct 7 ms 5068 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 6 ms 4992 KB Output is correct
14 Correct 8 ms 4992 KB Output is correct
15 Correct 8 ms 4992 KB Output is correct
16 Correct 7 ms 4992 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 8 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 7 ms 4992 KB Output is correct
21 Correct 7 ms 4992 KB Output is correct
22 Correct 7 ms 4992 KB Output is correct
23 Correct 6 ms 4992 KB Output is correct
24 Correct 7 ms 4992 KB Output is correct
25 Correct 8 ms 4992 KB Output is correct
26 Correct 7 ms 4992 KB Output is correct
27 Incorrect 7 ms 4992 KB Unexpected end of file - token expected
28 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 54 ms 13572 KB Output is correct
2 Correct 7 ms 5376 KB Output is correct
3 Correct 35 ms 9208 KB Output is correct
4 Correct 39 ms 12280 KB Output is correct
5 Correct 116 ms 14196 KB Output is correct
6 Correct 135 ms 11256 KB Output is correct
7 Correct 115 ms 14480 KB Output is correct
8 Correct 20 ms 8832 KB Output is correct
9 Correct 17 ms 8576 KB Output is correct
10 Correct 108 ms 14456 KB Output is correct
11 Correct 81 ms 12788 KB Output is correct
12 Correct 114 ms 12156 KB Output is correct
13 Incorrect 9 ms 5760 KB Unexpected end of file - token expected
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 4964 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 8 ms 4992 KB Output is correct
11 Correct 7 ms 5068 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 6 ms 4992 KB Output is correct
14 Correct 8 ms 4992 KB Output is correct
15 Correct 8 ms 4992 KB Output is correct
16 Correct 7 ms 4992 KB Output is correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 8 ms 4992 KB Output is correct
19 Correct 6 ms 4992 KB Output is correct
20 Correct 7 ms 4992 KB Output is correct
21 Correct 7 ms 4992 KB Output is correct
22 Correct 7 ms 4992 KB Output is correct
23 Correct 6 ms 4992 KB Output is correct
24 Correct 7 ms 4992 KB Output is correct
25 Correct 8 ms 4992 KB Output is correct
26 Correct 7 ms 4992 KB Output is correct
27 Incorrect 7 ms 4992 KB Unexpected end of file - token expected
28 Halted 0 ms 0 KB -