oj.uz

Submission #657729

# Submission time Handle Problem Language Result Execution time Memory
657729 2022-11-10T21:24:30 Z inksamurai Alternating Current (BOI18_alternating) C++17
19 / 100
 32 ms 6468 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3NRqilq ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define nare {cout<<"impossible\n";exit(0);}

signed main(){
_3NRqilq;
	int n,m;
	cin>>n>>m;
	vec(vec(pii)) adqry(n);
	rep(i,m){
		int l,r;
		cin>>l>>r;
		assert(l<=r);
		l-=1,r-=1;
		adqry[l].pb({r,i});
	}
	vi pns(m);
	vec(pii) _lst(2);
	// index,id
	_lst[0].fi=-1;
	_lst[0].se=0;
	_lst[1].fi=-1;
	_lst[1].se=1;
	rep(i,n){
		for(auto p:adqry[i]){
			int r=p.fi;
			int j=p.se;
			if(r>_lst[0].fi){
				swap(_lst[0],_lst[1]);
				_lst[0].fi=r;
				pns[j]=_lst[0].se;
			}else if(r>_lst[1].fi){
				_lst[1].fi=r;
				pns[j]=_lst[1].se;
			}
			if(_lst[0].fi<_lst[1].fi){
				swap(_lst[0],_lst[1]);
			}
		}
		rep(j,2){
			if(i>_lst[j].fi){
				nare;
			}
		}
	}
	string _s;
	rep(i,m){
		_s+=(char)(pns[i]+'0');
	}
	print(_s);
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4152 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 11 ms 4436 KB Output is correct
4 Correct 11 ms 4564 KB Output is correct
5 Correct 32 ms 5560 KB Output is correct
6 Correct 23 ms 5252 KB Output is correct
7 Correct 25 ms 5856 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2516 KB Output is correct
10 Correct 27 ms 5648 KB Output is correct
11 Correct 20 ms 5128 KB Output is correct
12 Correct 28 ms 6008 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 24 ms 5232 KB Output is correct
16 Correct 14 ms 4956 KB Output is correct
17 Correct 25 ms 6468 KB Output is correct
18 Correct 18 ms 3412 KB Output is correct
19 Correct 2 ms 2888 KB Output is correct
20 Correct 23 ms 4800 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -