oj.uz

Submission #70733

# Submission time Handle Problem Language Result Execution time Memory
70733 2018-08-23T09:22:10 Z khohko Alternating Current (BOI18_alternating) C++17
0 / 100
 119 ms 11604 KB 
#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][2];

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;
	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;
	}
	else
		for(int i=0; i<m; i++)pas[i]=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;
		pas[mk.sc]=1;
		v.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}});
			else
				v.pb({a[i].fr,{a[i].sc.fr,i}});
		}

		sort(v.begin(),v.end());
	//	for(auto x:v){
	//		cout<<x.fr<<" - "<<x.sc.fr<<endl;
	//	}
		ma=0,mb=0,j=0;
		ma=a[mx.sc].sc.fr;
		mb=mk.fr;
		//cout<<ma<<" "<<mb<<endl;
		st.clear();
		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());
	//		cout<<i<<" "<<ma<<" "<<mb<<" "<<st.size()<<endl;
			//if(ma>mb){
			if(ma<i&&mb<i){
				if(!st.size()){
						e=0;
						break;
					}
					ma=(--st.end())->fr;
					pas[(--st.end())->sc]=0;
					st.erase((--st.end()));
					if(!st.size()){
						e=0;
						break;
					}
					mb=st.begin()->fr;
					pas[st.begin()->sc]=1;
					st.erase(st.begin());

			}
			else {
				if(i<ld&&mb<i){
					if(!st.size()){
						e=0;
						break;
					}
					mb=st.begin()->fr;
					pas[st.begin()->sc]=1;
					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(e){
			for(int i=0; i<m; i++)cout<<pas[i];
			return 0;
		}
	}


	eend();
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:73: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:143:11: 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:56:5: warning: unused variable 'la' [-Wunused-variable]
  ll la=-MAX;
     ^~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Incorrect 3 ms 416 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Incorrect 3 ms 416 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Incorrect 3 ms 416 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 11604 KB Output is correct
2 Correct 3 ms 11604 KB Output is correct
3 Correct 51 ms 11604 KB Output is correct
4 Correct 85 ms 11604 KB Output is correct
5 Incorrect 119 ms 11604 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Incorrect 3 ms 416 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -