Submission #1313143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313143		SugarCubes69	Alternating Current (BOI18_alternating)	C++20	0 / 100	24 ms	7768 KiB

alternating

//edi subtask 4

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn = 1e5+5;

ll N,M,a[maxn],b[maxn];
vector<pair<ll,ll>> pr[maxn];
ll ans[maxn];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> N >> M;
    for(int i=0;i<M;i++) cin >> a[i] >> b[i];

    for(int i=0;i<M;i++) pr[a[i]].push_back({b[i],i});
    for(int i=1;i<=N;i++) sort(pr[i].begin(),pr[i].end());
    ll cur1 = 1,cur2 = 1;
    for(int i=1;i<=N;i++){
        if(min(cur1,cur2)<i){
            cout << "impossible";
            return 0;
        }
        for(pair<ll,ll> j:pr[i]){
            if(cur1<=cur2){
                cur1 = max(cur1,j.first+1);
                ans[j.second] = 0;
            }
            else{
                cur2 = max(cur2,j.first+1);
                ans[j.second] = 1;
            }
        }
    }
    for(int i=0;i<M;i++) cout << ans[i];
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26