oj.uz

Submission #127525

# Submission time Handle Problem Language Result Execution time Memory
127525 2019-07-09T13:42:16 Z mechfrog88 Alternating Current (BOI18_alternating) C++14
0 / 100
 3000 ms 3576 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
 
vector <pair<ll,ll>> arr;
vector <bool> ans;
ll n,m;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	arr.resize(m);
	for (int z=0;z<m;z++){
		cin >> arr[z].first >> arr[z].second;
	}
	vector <ll> seg(n+1,0);
	ans.resize(m);
	for (int z=0;z<m;z++){
		ll l = arr[z].first;
		ll r = arr[z].second;
		seg[r]++;
		while (l != r){
			seg[l]++;
			l++;
			if (l == n+1){
				l = 1;
			}
		}
	}
	for (int z=0;z<m;z++){
		ll l = arr[z].first;
		ll r = arr[z].second;
		bool ok = true;
		while (l != r){
			if (seg[l] <= 1){
				ok = false;
				break;  
			}
			l++;
			if (l == n+1){
				l = 1;
			}
		}
		if (!ok) continue;
		l = arr[z].first;
		r = arr[z].second;
		seg[r]--;
		while (l != r){
			seg[l]--;
			l++;
			if (l == n+1){
				l = 1;
			}
		}
		ans[z] = true;
	}
	vector <pair<bool,bool>> check(n+1);
	for (int z=0;z<=n;z++){
		check[z].first = false;
		check[z].second = false;
	}
	for (ll z=0;z<m;z++){
		if (ans[z]){
			ll l = arr[z].first;
			ll r = arr[z].second;
			check[r].first = true;
			while (l != r){
				check[l].first = true;
				l++;
				if (l == n+1){
					l = 1;
				}
			}
		} else {
			ll l = arr[z].first;
			ll r = arr[z].second;
			check[r].second = true;
			while (l != r){
				check[l].second = true;
				l++;
				if (l == n+1){
					l = 1;
				}
			}
		}
	}
	for (int z=1;z<=n;z++){
		if (!check[z].first || !check[z].second){
			cout << "impossible" << endl;
			return 0;
		}
	}
	for (bool i : ans){
		cout << i;
	} cout << endl;
}

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 Incorrect 2 ms 376 KB 'impossible' claimed, but there is a solution
4 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 Incorrect 2 ms 376 KB 'impossible' claimed, but there is a solution
4 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 Incorrect 2 ms 376 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 3576 KB Time limit exceeded
2 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 Incorrect 2 ms 376 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -