# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
566335 | 2022-05-22T08:54:16 Z | Abdulmohsen1284 | Bootfall (IZhO17_bootfall) | C++14 | 416 ms | 262144 KB |
#include"bits/stdc++.h" using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class x> using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); bool plc[20000]; long long occ[20000],a[505]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); long long n,sum=0; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; sum+=a[i]; } plc[0]=true; vector <int> h; vector <int> yes; yes.push_back(0); for(int i=0;i<n;i++) { for(int j=yes.size()-1;j>=0;j--) { if(plc[yes[j]+a[i]]!=true||(yes[j]+a[i])<=20000){ plc[yes[j]+a[i]]=true; yes.push_back(yes[j]+a[i]); } } } //cout<<"HI"<<endl; if(plc[sum/2]&&sum%2==0) { for(int k=0;k<n;k++) { sum-=a[k]; for(int i=0;i<=20000;i++) plc[i]=false; plc[0]=true; yes.clear(); yes.push_back(0); for(int i=0;i<n;i++) { if(i==k) continue; for(int j=yes.size()-1;j>=0;j--) { if(plc[yes[j]+a[i]]!=true||(yes[j]+a[i])<=20000){ plc[yes[j]+a[i]]=true; yes.push_back(yes[j]+a[i]); } } } //cout<<"HELLO"<<endl; for(int i=0;i<=sum;i++) { long long oth=i-(sum-i); if(oth<=0||oth>=20000) continue; if(plc[i]){ occ[oth]++; //cout<<oth<<" "; } } //cout<<endl; sum+=a[k]; } } for(int i=1;i<=20000;i++) { if(occ[i]==n){ //cout<<"???"<<endl; h.push_back(i); } } cout<<h.size()<<"\n"; for(auto i : h) cout<<i<<" "; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Runtime error | 416 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Runtime error | 416 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Runtime error | 416 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Runtime error | 416 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Runtime error | 416 ms | 262144 KB | Execution killed with signal 9 |
11 | Halted | 0 ms | 0 KB | - |