Submission #63228

#	Time	Username	Problem	Language	Result	Execution time	Memory
63228		khsoo01	Alternating Current (BOI18_alternating)	C++11	100 / 100	222 ms	17260 KiB

alternating

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int N = 100005, inf = 1e9;

int n, m, s[N], nxt[N], opt[N];
bool non[N];

pii a[N];

vector<int> ans, in[N], out[N];

set<pii> st, ss, es;

void boom () {
	puts("impossible");
	exit(0);
}

void solve (vector<pair<pii, int> > &V, vector<int> &X) {
	int DI;
	for(auto &T : V) {
		int S = T.X.X, E = T.X.Y, I = T.Y;
		if(E == n) {
			st.insert({S, I});
			DI = I;
		}
		else {
			int J = upper_bound(X.begin(), X.end(), E) - X.begin() - 1;
			if(J < 0 || X[J] < S) J = S;
			else J = X[J];
			auto it = st.lower_bound({J+1, 0});
			if(it != st.end() && (it->X) <= E+1) {
				st.insert({S, I});
				nxt[I] = (it->Y);
			}
		}
	}
	if(!nxt[DI]) boom();
	ans.push_back(DI);
	for(int i=nxt[DI];i!=DI;i=nxt[i]) {
		ans.push_back(i);
	}
}

void eliminate () {
	for(auto &T : ans) {
		if(a[T].X > a[T].Y) in[1].push_back(T);
		out[a[T].Y+1].push_back(T);
		in[a[T].X].push_back(T);
	}
	for(int i=1;i<=n;i++) {
		for(auto &T : out[i]) {
			int S = a[T].X, E = a[T].Y;
			if(S > E) S -= n;
			auto it = ss.find({S, T});
			if(it != ss.end()) ss.erase(it);
			it = es.find({E, T});
			if(it != es.end()) es.erase(it);
		}
		for(auto &T : in[i]) {
			if(non[T]) continue;
			int S = a[T].X, E = a[T].Y;
			if(S > E) {
				if(i == 1) S -= n;
				else E += n;
			}
			ss.insert({S, T});
			es.insert({E, T});
		}
		if(ss.size() > 2) {
			auto si = ss.begin(), ei = es.end();
			ei--;
			int A = si->Y, B = ei->Y;
			set<pii> SS, ES;
			for(auto &T : ss) {
				int I = T.Y;
				if(A == I || B == I) SS.insert(T);
				else non[I] = true;
			}
			for(auto &T : es) {
				int I = T.Y;
				if(A == I || B == I) ES.insert(T);
				else non[I] = true;
			}
			swap(SS, ss);
			swap(ES, es);
		}
	}
	vector<int> ANS;
	for(auto &T : ans) {
		if(!non[T]) ANS.push_back(T);
	}
	swap(ANS, ans);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		scanf("%d%d",&a[i].X,&a[i].Y);
		if(a[i].X <= a[i].Y) {
			s[a[i].X]++;
			s[a[i].Y+1]--;
		}
		else {
			s[1]++;
			s[a[i].Y+1]--;
			s[a[i].X]++;
		}
	}
	int MV = inf, MI;
	for(int i=1;i<=n;i++) {
		s[i] += s[i-1];
		if(MV > s[i]) {
			MV = s[i];
			MI = i;
		}
	}
	if(MV < 2) boom();
	else if(MV == 2) {
		vector<pair<pii, int> > V, O;
		vector<int> X;
		for(int i=1;i<=m;i++) {
			a[i].X -= MI;
			a[i].Y -= MI;
			if(a[i].X <= 0) a[i].X += n;
			if(a[i].Y <= 0) a[i].Y += n;
			if(a[i].X > a[i].Y || (a[i].X <= n && n <= a[i].Y)) {
				O.push_back({{a[i].X, (a[i].Y == n ? 0 : a[i].Y)}, i});
			}
			else V.push_back({a[i], i});
		}
		V.push_back({{0, O[0].X.Y}, O[0].Y});
		V.push_back({{O[0].X.X, n}, O[0].Y});
		sort(V.begin(), V.end());
		reverse(V.begin(), V.end());
		for(int i=1;i<n;i++) {
			int I = (i + MI > n ? i + MI - n : i + MI);
			if(s[I] == 2) X.push_back(i);
		}
		solve(V, X);
	}
	else {
		for(int i=1;i<=m;i++) {
			ans.push_back(i);
		}
	}
	eliminate();
	for(auto &T : ans) {
		opt[T] = 1;
	}
	for(int i=1;i<=m;i++) {
		printf("%d",opt[i]);
	}
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
alternating.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a[i].X,&a[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:142:15: warning: 'MI' may be used uninitialized in this function [-Wmaybe-uninitialized]
    int I = (i + MI > n ? i + MI - n : i + MI);
             ~~^~~~

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