# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
333793 | 2020-12-07T19:33:58 Z | bigDuck | Detecting Molecules (IOI16_molecules) | C++14 | 1 ms | 384 KB |
#include "molecules.h" #include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount ll p[200010]; std::vector<int> find_subset(int l, int u, std::vector<int> w0) { vector<int> res; ll n=w0.size(); vector<pii> w; for(int i=0; i<w0.size();i++ ){ w.pb({w0[i], i}); } sort(w.begin(), w.end()); for(int i=1; i<=n ;i++){ p[i]=p[i-1]+w[i-1].ft; } if( (p[n]>=l) && (p[n]<=u) ){ for(int i=0; i<n; i++){res.pb(w[i].sc);} return res; } if( (p[n]<l) || (p[1]>u) ){return res;} int r=0; for(int i=1; i<=n; i++){ if( (p[i]>=l) && (p[i]<=u) ){ for(int j=0; j<i; j++){res.pb(w[j].sc);} return res; } if( (p[i]>u) && (( ( (i%2)==0) && ( (p[i]-p[i/2])>=l ) )||( ( (i%2)==1 ) && ( (p[i]-p[((int)i/2)])>=l ) ) ) && (p[i/2]<u) ) { r=i; break; } } if(r==0){return res;} int mid=r/2; int cnt=0; ll sum=p[mid]; while(sum<l){ cnt++; sum-=w[cnt-1].ft; sum+=w[r-cnt].ft; } for(int i=(cnt+1); i<=mid; i++){ res.pb(w[i-1].sc); } for(int i=r-cnt+1; i<=r; i++){ res.pb(w[i-1].sc); } return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | OK (n = 1, answer = NO) |
2 | Correct | 1 ms | 384 KB | OK (n = 1, answer = NO) |
3 | Correct | 0 ms | 364 KB | OK (n = 1, answer = YES) |
4 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
5 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
6 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
7 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
8 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
9 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
10 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
11 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
12 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
13 | Incorrect | 0 ms | 364 KB | Integer 4 violates the range [0, 3] |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 364 KB | item #0 is taken twice |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | OK (n = 1, answer = NO) |
2 | Correct | 1 ms | 384 KB | OK (n = 1, answer = NO) |
3 | Correct | 0 ms | 364 KB | OK (n = 1, answer = YES) |
4 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
5 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
6 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
7 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
8 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
9 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
10 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
11 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
12 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
13 | Incorrect | 0 ms | 364 KB | Integer 4 violates the range [0, 3] |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | OK (n = 1, answer = NO) |
2 | Correct | 1 ms | 384 KB | OK (n = 1, answer = NO) |
3 | Correct | 0 ms | 364 KB | OK (n = 1, answer = YES) |
4 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
5 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
6 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
7 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
8 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
9 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
10 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
11 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
12 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
13 | Incorrect | 0 ms | 364 KB | Integer 4 violates the range [0, 3] |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | OK (n = 1, answer = NO) |
2 | Correct | 1 ms | 384 KB | OK (n = 1, answer = NO) |
3 | Correct | 0 ms | 364 KB | OK (n = 1, answer = YES) |
4 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
5 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
6 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
7 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
8 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
9 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
10 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
11 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
12 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
13 | Incorrect | 0 ms | 364 KB | Integer 4 violates the range [0, 3] |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | OK (n = 1, answer = NO) |
2 | Correct | 1 ms | 384 KB | OK (n = 1, answer = NO) |
3 | Correct | 0 ms | 364 KB | OK (n = 1, answer = YES) |
4 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
5 | Correct | 1 ms | 364 KB | OK (n = 2, answer = YES) |
6 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
7 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
8 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
9 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
10 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
11 | Correct | 1 ms | 364 KB | OK (n = 3, answer = YES) |
12 | Correct | 0 ms | 364 KB | OK (n = 3, answer = YES) |
13 | Incorrect | 0 ms | 364 KB | Integer 4 violates the range [0, 3] |
14 | Halted | 0 ms | 0 KB | - |