oj.uz

Submission #171287

# Submission time Handle Problem Language Result Execution time Memory
171287 2019-12-28T07:49:05 Z Atalasion Alternating Current (BOI18_alternating) C++14
19 / 100
 150 ms 16612 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int n, m, ans[N], R[N];
vector<pii> vl[N], vr[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int l, r;
		cin >> l >> r;
		R[i] = r;
		vl[l].pb({r, i});
		vr[r].pb({r, i});
	}
	int mx1 = 0, mx2 = 0;
	set<pii> st;
	for (int i = 1; i <= n; i++){
		for (auto u:vl[i]){
			st.insert(u);
		}
		if (R[mx1] == i - 1){
			if (st.size() == 0) return cout << "impossible", 0;
			mx1 = st.rbegin()->S;
			ans[mx1] = 1;
			st.erase(*st.rbegin());
		}
		if (R[mx2] == i - 1){
			if (st.size() == 0) return cout << "impossible", 0;
			mx2 = st.rbegin()->S;
			ans[mx2] = 0;
			st.erase(*st.rbegin());
		}
		for (auto u:vr[i]){
			st.erase(u);
		}
	}
	for (int i = 1; i <= m; i++) cout << ans[i];











	return 0;
}

Compilation message

alternating.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
alternating.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Incorrect 10 ms 9720 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 11 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Incorrect 10 ms 9720 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 11 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Incorrect 10 ms 9720 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 68 ms 16612 KB Output is correct
2 Correct 11 ms 9744 KB Output is correct
3 Correct 29 ms 13176 KB Output is correct
4 Correct 48 ms 15556 KB Output is correct
5 Correct 102 ms 15216 KB Output is correct
6 Correct 107 ms 15008 KB Output is correct
7 Correct 133 ms 15712 KB Output is correct
8 Correct 16 ms 10104 KB Output is correct
9 Correct 12 ms 9848 KB Output is correct
10 Correct 108 ms 15444 KB Output is correct
11 Correct 82 ms 14456 KB Output is correct
12 Correct 101 ms 16180 KB Output is correct
13 Correct 7 ms 9720 KB Output is correct
14 Correct 15 ms 9720 KB Output is correct
15 Correct 109 ms 14752 KB Output is correct
16 Correct 46 ms 15740 KB Output is correct
17 Correct 150 ms 16468 KB Output is correct
18 Correct 108 ms 15096 KB Output is correct
19 Correct 15 ms 10104 KB Output is correct
20 Correct 61 ms 13944 KB Output is correct

Subtask #5
0 / 26.0

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