Submission #127525

#	Time	Username	Problem	Language	Result	Execution time	Memory
127525		mechfrog88	Alternating Current (BOI18_alternating)	C++14	0 / 100	3029 ms	3576 KiB

alternating

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26