# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
574709 | 2022-06-09T09:45:20 Z | KrisjanisP | Handcrafted Gift (IOI20_gift) | C++14 | 225 ms | 28716 KB |
#include "gift.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> ii; void compress(vector<ii>& one) { sort(one.begin(),one.end()); vector<ii> newOne; newOne.push_back(one[0]); for(ll i=1;i<one.size();i++) { if(one[i].first<=newOne.back().second) newOne.back().second=max(newOne.back().second,one[i].second); else newOne.push_back(one[i]); } one = newOne; } int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) { vector<ii> one, two; for(ll i=0;i<r;i++) { if(x[i]==1) one.push_back({a[i],b[i]}); else two.push_back({a[i],b[i]}); } if(one.size()) compress(one); vector<bool> same(n,false); for(ll i=0;i<one.size();i++) { for(ll j=one[i].first+1;j<=one[i].second;j++) same[j]=true; } vector<ll> vec(n,0); vec[0]=0; for(ll i=1;i<n;i++) { if(same[i]) vec[i]=vec[i-1]; else vec[i]=1-vec[i-1]; } vector<ll> ps(n,0); ps[0]=vec[0]; for(ll i=1;i<n;i++) ps[i]=ps[i-1]+vec[i]; bool found = false; for(ll i=0;i<two.size();i++) { ll sum = ps[two[i].second]; if(two[i].first) sum-=ps[two[i].first]; if(sum==0||sum==(two[i].second-two[i].first+1)) { found=true; break; } } if(found) return 0; // answer doesn't exist std::string res(n, 'R'); for(ll i=0;i<n;i++) if(vec[i]) res[i]='B'; craft(res); return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 4 ms | 924 KB | Output is correct |
5 | Correct | 225 ms | 28660 KB | Output is correct |
6 | Correct | 184 ms | 28660 KB | Output is correct |
7 | Correct | 217 ms | 28664 KB | Output is correct |
8 | Correct | 183 ms | 28716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Incorrect | 4 ms | 852 KB | Possible does not match answer file |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | Possible does not match answer file |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Incorrect | 1 ms | 340 KB | Possible does not match answer file |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 4 ms | 924 KB | Output is correct |
5 | Correct | 225 ms | 28660 KB | Output is correct |
6 | Correct | 184 ms | 28660 KB | Output is correct |
7 | Correct | 217 ms | 28664 KB | Output is correct |
8 | Correct | 183 ms | 28716 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Incorrect | 4 ms | 852 KB | Possible does not match answer file |
12 | Halted | 0 ms | 0 KB | - |