oj.uz

Submission #890564

# Submission time Handle Problem Language Result Execution time Memory
890564 2023-12-21T13:26:59 Z 1075508020060209tc Alternating Current (BOI18_alternating) C++14
19 / 100
 34 ms 9136 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 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 1 ms 4696 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 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 1 ms 4696 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 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 17 ms 8660 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 9 ms 4956 KB Output is correct
4 Correct 11 ms 7896 KB Output is correct
5 Correct 27 ms 8852 KB Output is correct
6 Correct 24 ms 5972 KB Output is correct
7 Correct 26 ms 8784 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 30 ms 8852 KB Output is correct
11 Correct 23 ms 8372 KB Output is correct
12 Correct 25 ms 8664 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 30 ms 9136 KB Output is correct
16 Correct 14 ms 7892 KB Output is correct
17 Correct 32 ms 8944 KB Output is correct
18 Correct 29 ms 8888 KB Output is correct
19 Correct 3 ms 4456 KB Output is correct
20 Correct 34 ms 9112 KB Output is correct

Subtask #5
0 / 26.0

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