oj.uz

답안 #70668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70668 2018-08-23T08:23:05 Z khohko Alternating Current (BOI18_alternating) C++17
0 / 100
 113 ms 11480 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};
	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}});
			mk=max({a[i].sc.fr,i},mk);
		}
	}
	ld=a[mk.sc].fr;
	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(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:136: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:56:5: warning: unused variable 'la' [-Wunused-variable]
  ll la=-MAX;
     ^~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 3 ms 560 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 3 ms 560 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 3 ms 560 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 11480 KB Output is correct
2 Correct 3 ms 11480 KB Output is correct
3 Incorrect 64 ms 11480 KB no wires in direction 1 between segments 1 and 100000
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Incorrect 3 ms 560 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -