oj.uz

Submission #70598

# Submission time Handle Problem Language Result Execution time Memory
70598 2018-08-23T07:13:55 Z khohko Alternating Current (BOI18_alternating) C++17
19 / 100
 166 ms 9160 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);
}

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.fr;
		a[i].sc.sc=i;
	}
	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++;
		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 2 ms 376 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Incorrect 2 ms 464 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 2 ms 376 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Incorrect 2 ms 464 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 2 ms 376 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Incorrect 2 ms 464 KB 'impossible' claimed, but there is a solution
4 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 9160 KB Output is correct
2 Correct 3 ms 9160 KB Output is correct
3 Correct 40 ms 9160 KB Output is correct
4 Correct 62 ms 9160 KB Output is correct
5 Correct 142 ms 9160 KB Output is correct
6 Correct 92 ms 9160 KB Output is correct
7 Correct 119 ms 9160 KB Output is correct
8 Correct 8 ms 9160 KB Output is correct
9 Correct 4 ms 9160 KB Output is correct
10 Correct 116 ms 9160 KB Output is correct
11 Correct 104 ms 9160 KB Output is correct
12 Correct 83 ms 9160 KB Output is correct
13 Correct 3 ms 9160 KB Output is correct
14 Correct 3 ms 9160 KB Output is correct
15 Correct 92 ms 9160 KB Output is correct
16 Correct 65 ms 9160 KB Output is correct
17 Correct 166 ms 9160 KB Output is correct
18 Correct 154 ms 9160 KB Output is correct
19 Correct 9 ms 9160 KB Output is correct
20 Correct 118 ms 9160 KB Output is correct

Subtask #5
0 / 26.0

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