Submission #70756

#	Time	Username	Problem	Language	Result	Execution time	Memory
70756		khohko	Alternating Current (BOI18_alternating)	C++17	0 / 100	252 ms	11472 KiB

alternating

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e12+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;

ll n,m;
pair<ll,pair<ll,ll> > a[ARRS];
ll pas[ARRS];

void eend(){
	cout<<"impossible";
	exit(0);
}

void rot(ll x){
	for(int i=0; i<m; i++){
		a[i].fr=(a[i].fr+n-1-x)%n+1;
		a[i].sc.fr=(a[i].sc.fr+n-1-x)%n+1;
	}
}
ll f[ARRS];

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	cin>>n>>m;
	pair<ll,ll> mx={-1,0};
	for(int i=0; i<m; i++){
		cin>>a[i].fr>>a[i].sc.fr;
		if(a[i].fr<=a[i].sc.fr)
			mx=max(mx,{a[i].sc.fr-a[i].fr,i});
		else
			mx=max(mx,{n-(a[i].fr-a[i].sc.fr)+1,i});
		a[i].sc.sc=i;
	}
//	cout<<mx.sc<<endl;
	rot(a[mx.sc].fr-1);
//	for(int i=0; i<m; i++){
//		cout<<a[i].fr<<" "<<a[i].sc.fr<<endl;
//	}

	ll la=-MAX;
	vector<pair<ll,pair<ll,ll> > > v;
	vector<pair<ll,pair<ll,ll> > > v1;
	for(int i=0; i<m; i++){
		if(i==mx.sc)continue;
		if(a[i].fr>a[i].sc.fr)
			v.pb({a[i].fr,{n,i}});
		else
			v.pb({a[i].fr,{a[i].sc.fr,i}});
	}

	sort(v.begin(),v.end());
	ll ma=0,mb=0,j=0;

	ma=a[mx.sc].sc.fr;
	multiset<pair<ll,ll> > st;
	bool e=1;
	for(int i=1; i<=n; i++){
		while(j<v.size()&&v[j].fr==i)st.insert(v[j].sc),j++;
		while(st.size()&&st.begin()->fr<i)st.erase(st.begin());
		if(ma<i){
			if(!st.size()){
				e=0;
				break;
			}
			ma=st.begin()->fr;
			pas[st.begin()->sc]=0;
			st.erase(st.begin());
		}
		if(mb<i){
			if(!st.size()){
				e=0;
				break;
			}
			mb=st.begin()->fr;
			pas[st.begin()->sc]=1;
			st.erase(st.begin());
		}
	}
	if(e){
		for(int i=0; i<m; i++)cout<<pas[i];
		return 0;
	}


//	vector<pair<ll,pair<ll,ll> > > v;
	ll ld;
	pair<ll,ll> mk={-1,-1};
	vector<ll> t;

	for(int i=0; i<m; i++){
		if(i==mx.sc)continue;
		if(a[i].fr>a[i].sc.fr){
//			v.pb({a[i].fr,{n,i}});
			t.pb(i);
			mk=max({a[i].sc.fr,i},mk);
		}
	}
	for(auto ix:t){
		mk.sc=ix;
		mk.fr=a[ix].sc.fr;
		ld=a[mk.sc].fr;
		//ld=MAX;
		for(int i=0; i<m; i++)pas[i]=0;
		pas[mk.sc]=1;
		v.clear();
		v1.clear();
	//	cout<<mk.fr<<" "<<mk.sc<<" "<<ld<<endl;
		for(int i=0; i<m; i++){
			if(i==mx.sc)continue;
			if(i==mk.sc)continue;
			if(a[i].fr>a[i].sc.fr)
				v.pb({a[i].fr,{n,i}}),
				v1.pb({n,{a[i].fr,i}});
			else
				v.pb({a[i].fr,{a[i].sc.fr,i}}),
				v1.pb({a[i].sc.fr,{a[i].fr,i}});
		}

		sort(v.begin(),v.end());
		sort(v1.begin(),v1.end());
	//	reverse(v1.begin(),v1.end());

		ll la=a[mx.sc].sc.fr,lb=mk.fr,ra=n+1,rb=a[mk.sc].fr;

		ll i=0,j=v1.size()-1;
		set<pair<ll,ll> > sa;
		set<pair<ll,ll> > sb;

		ll e=1;
		while(min(la,lb)+1<max(ra,rb)){
			//cout<<la<<" "<<lb<<"  "<<ra<<" "<<rb<<endl;
			while(i<v.size()&&v[i].fr<=min(la,lb)+1){
				sa.insert(v[i].sc);
				i++;
			}

			while(j>=0&&v1[j].fr>=max(ra,rb)-1){
				sb.insert(v1[j].sc);
				j--;
			}

			if(!sa.size()&&!sb.size()){e=0;break;}
			if(la==lb){
				while(sb.size()&&f[(--sb.end())->sc])sb.erase((--sb.end()));
				if(sb.size()){
					if(ra<=rb){
						rb=(--sb.end())->fr;
						pas[(--sb.end())->sc]=1;
						f[(--sb.end())->sc]=1;
						sb.erase((--sb.end()));
					}
					else {
						ra=(--sb.end())->fr;
						pas[(--sb.end())->sc]=0;
						f[(--sb.end())->sc]=1;
						sb.erase((--sb.end()));
					}
				}
			}
			while(sa.size()&&f[sa.begin()->sc])sa.erase(sa.begin());
			if(sa.size()){
				if(la>=lb){
					lb=sa.begin()->fr;
					pas[sa.begin()->sc]=1;
					f[sa.begin()->sc]=1;
					sa.erase(sa.begin());
				}
				else {
					la=sa.begin()->fr;
					pas[sa.begin()->sc]=0;
					f[sa.begin()->sc]=1;
					sa.erase(sa.begin());
				}
			}

			while(sb.size()&&f[(--sb.end())->sc])sb.erase((--sb.end()));
			if(sb.size()){
				if(ra<=rb){
					rb=(--sb.end())->fr;
					pas[(--sb.end())->sc]=1;
					f[(--sb.end())->sc]=1;
					sb.erase((--sb.end()));
				}
				else {
					ra=(--sb.end())->fr;
					pas[(--sb.end())->sc]=0;
					f[(--sb.end())->sc]=1;
					sb.erase((--sb.end()));
				}
			}

			if(la+1>=ra)la=n+1,ra=0;
			if(lb+1>=rb)lb=n+1,rb=0;
		}

		if(e){
			for(int i=0; i<m; i++)cout<<pas[i];
			return 0;
		}

	}


	eend();
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:74:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<v.size()&&v[j].fr==i)st.insert(v[j].sc),j++;
         ~^~~~~~~~~
alternating.cpp:148:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(i<v.size()&&v[i].fr<=min(la,lb)+1){
          ~^~~~~~~~~
alternating.cpp:56:5: warning: unused variable 'la' [-Wunused-variable]
  ll la=-MAX;
     ^~
alternating.cpp:102:5: warning: variable 'ld' set but not used [-Wunused-but-set-variable]
  ll ld;
     ^~

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