Submission #171287

#	Time	Username	Problem	Language	Result	Execution time	Memory
171287		Atalasion	Alternating Current (BOI18_alternating)	C++14	19 / 100	150 ms	16612 KiB

alternating

//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 (stderr)

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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26