Submission #890564

#	Time	Username	Problem	Language	Result	Execution time	Memory
890564		1075508020060209tc	Alternating Current (BOI18_alternating)	C++14	19 / 100	34 ms	9136 KiB

alternating

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;int m;
vector<int>vca;vector<int>vcb;
pair<int,int>ar[200005];
int qar[200005];
bool cmp(int i,int j){
if(ar[i].first<ar[j].first){return 1;}
if(ar[i].first>ar[j].first){return 0;}
return ar[i].second<ar[j].second;
}
int ans[2000005];

signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
    cin>>ar[i].first>>ar[i].second;
    qar[i]=i;
}
sort(qar+1,qar+m+1,cmp);
int va=0;int vb=0;
for(int i=1;i<=m;i++){
    pair<int,int>pr=ar[qar[i]];
    if(va>vb){
        swap(va,vb);
        swap(vca,vcb);
    }
    if(va+1<pr.first){
        cout<<"impossible\n";return 0;
    }
    va=max(va,pr.second);
    vca.push_back(qar[i]);
}
for(int i=0;i<vca.size();i++){
    ans[vca[i]]=1;
}
if(va+vb!=n+n){  cout<<"impossible\n";return 0; }
for(int i=1;i<=m;i++){
    cout<<ans[i];
}

}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:38:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 | for(int i=0;i<vca.size();i++){
      |             ~^~~~~~~~~~~

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