Submission #1188668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188668		kl0989e	Alternating Current (BOI18_alternating)	C++20	0 / 100	14 ms	2884 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()

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 ord(m);
	iota(all(ord),0);
	sort(all(ord),[&](int a, int b){return inte[a]<inte[b];});
	vi col(m,-1);
	int l=0,r=0;
	for (int i=0; i<m; i++) {
		if (l<r) {
			col[ord[i]]=0;
			l=max(l,inte[ord[i]].se);
		}
		else {
			col[ord[i]]=1;
			r=max(r,inte[ord[i]].se);
		}
	}
	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) {
		for (int i=0; i<m; i++) {
			cout << col[i];
		}
		cout << '\n';
	}
	else {
		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