Submission #1188614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188614		kl0989e	Alternating Current (BOI18_alternating)	C++20	0 / 100	3095 ms	5192 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--;
	}
	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 (col[i]!=-1) {
			continue;
		}
		for (int j=0; j<m; j++) {
			if (i==j) {
				continue;
			}
			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;});
	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';
	return 0;
}

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