Submission #1188653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188653		kl0989e	Alternating Current (BOI18_alternating)	C++20	0 / 100	3092 ms	5572 KiB

alternating

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

bool con(int a, int b, int c, int d, int m) {
	if (b<a) {
		return (con(a,m-1,c,d,m)&con(0,b,c,d,m));
	}
	else if (d<c) {
		return (con(a,b,c,m-1,m)|con(a,b,0,d,m));
	}
	return (c<=a && b<=d);
}

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	vector<pi> inte(m);
	for (int i=0; i<m; i++) {
		cin >> inte[i].fi >> inte[i].se;
		inte[i].fi--;
		inte[i].se--;
		if ((inte[i].se+1)%n==inte[i].fi) {
			inte[i]={0,n-1};
		}
	}
	vi col(m,-1);
	vi inv_of(m,-1);
	vector<vi> to(m);
	vi rem;
	for (int i=0; i<m; i++) {
		if (col[i]!=-1) {
			continue;
		}
		for (int j=0; j<m; j++) {
			if (i==j) {
				continue;
			}
			if (inte[i]==inte[j]) {
				col[i]=1;
				col[j]=0;
				break;
			}
			if (con(inte[i].fi,inte[i].se,inte[j].fi,inte[j].se,n)) {
				inv_of[i]=j;
				to[j].pb(i);
				break;
			}
		}
		if (inv_of[i]==-1) {
			rem.pb(i);
		}
	}
	sort(all(rem),[&](int a, int b){return inte[a].fi<inte[b].fi;});
	if (rem.size()%2==0) {
		for (int i=0; i<rem.size(); i++) {
			col[rem[i]]=i%2;
		}
		for (int i=0; i<m; i++) {
			if (inv_of[i]!=-1) {
				continue;
			}
			queue<pi> q;
			q.push({i,col[i]});
			while (q.size()) {
				auto [a,c]=q.front();
				q.pop();
				col[a]=c;
				for (auto t:to[a]) {
					q.push({t,c^1});
				}
			}
		}
		vi a(n+1,0),b(n+1,0);
		for (int i=0; i<m; i++) {
			if (col[i]) {
				if (inte[i].fi<=inte[i].se) {
					a[inte[i].fi]++;
					a[inte[i].se+1]--;
				}
				else {
					a[inte[i].fi]++;
					a[n]--;
					a[0]++;
					a[inte[i].se+1]--;
				}
			}
			else {
				if (inte[i].fi<=inte[i].se) {
					b[inte[i].fi]++;
					b[inte[i].se+1]--;
				}
				else {
					b[inte[i].fi]++;
					b[n]--;
					b[0]++;
					b[inte[i].se+1]--;
				}
			}
		}
		for (int i=0; i<n; i++) {
			if (i>0) {
				a[i]+=a[i-1];
				b[i]+=b[i-1];
			}
			if (a[i]==0 || b[i]==0) {
				cout << "impossible\n";
				return 0;
			}
		}
		for (int i=0; i<m; i++) {
			cout << col[i];
		}
		cout << '\n';
	}
	else {
		for (int i=0; i<rem.size(); i++) {
			for (int j=i; j!=i+1; j=(j+2)%rem.size()) {
				col[rem[j]]=0;
			}
			for (int j=i+1; j!=i; j=(j+2)%rem.size()) {
				col[rem[j]]=1;
			}
			for (int i=0; i<m; i++) {
				if (inv_of[i]!=-1) {
					continue;
				}
				queue<pi> q;
				q.push({i,col[i]});
				while (q.size()) {
					auto [a,c]=q.front();
					q.pop();
					col[a]=c;
					for (auto t:to[a]) {
						q.push({t,c^1});
					}
				}
			}
			vi a(n+1,0),b(n+1,0);
			for (int i=0; i<m; i++) {
				if (col[i]) {
					if (inte[i].fi<=inte[i].se) {
						a[inte[i].fi]++;
						a[inte[i].se+1]--;
					}
					else {
						a[inte[i].fi]++;
						a[n]--;
						a[0]++;
						a[inte[i].se+1]--;
					}
				}
				else {
					if (inte[i].fi<=inte[i].se) {
						b[inte[i].fi]++;
						b[inte[i].se+1]--;
					}
					else {
						b[inte[i].fi]++;
						b[n]--;
						b[0]++;
						b[inte[i].se+1]--;
					}
				}
			}
			bool ok=1;
			for (int i=0; i<n; i++) {
				if (i>0) {
					a[i]+=a[i-1];
					b[i]+=b[i-1];
				}
				if (a[i]==0 || b[i]==0) {
					ok=0;
				}
			}
			if (!ok) {
				continue;
			}
			for (int i=0; i<m; i++) {
				cout << col[i];
			}
			cout << '\n';
			return 0;
		}
		cout << "impossible\n";
	}
	return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26