oj.uz

Submission #70594

# Submission time Handle Problem Language Result Execution time Memory
70594 2018-08-23T07:06:47 Z khohko Alternating Current (BOI18_alternating) C++17
0 / 100
 135 ms 8460 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,ll> a[ARRS];
ll pas[ARRS];

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

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	cin>>n>>m;
	for(int i=0; i<m; i++){
		cin>>a[i].fr>>a[i].sc;
	}
	sort(a,a+m);
	ll ma=0,mb=0,j=0;
	multiset<pair<ll,ll> > st;
	for(int i=1; i<=n; i++){
		while(j<m&&a[j].fr==i)st.insert({a[j].sc,j}),j++;
		while(st.size()&&st.begin()->fr<i)st.erase(st.begin());
		if(ma<i){
			if(!st.size())eend();
			ma=st.begin()->fr;
			pas[st.begin()->sc]=1;
			st.erase(st.begin());
		}
		if(mb<i){
			if(!st.size())eend();
			mb=st.begin()->fr;
			pas[st.begin()->sc]=0;
			st.erase(st.begin());
		}

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



}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Incorrect 4 ms 480 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 4 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Incorrect 4 ms 480 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 4 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Incorrect 4 ms 480 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 135 ms 8460 KB Output is correct
2 Correct 4 ms 8460 KB Output is correct
3 Correct 39 ms 8460 KB Output is correct
4 Incorrect 70 ms 8460 KB no wires in direction 0 between segments 100000 and 100000
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

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