| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1072137 | 2024-08-23T14:53:21 Z | Itamar | Counting Mushrooms (IOI20_mushrooms) | C++14 | 1 ms | 344 KB |
using namespace std;
#include <vector>
#define ll long long
#define vll vector<ll>
#include<iostream>
#define vi vector<int>
int use_machine(std::vector<int> x);
#include<bitset>
const int k = 15;
int count_mushrooms(int n) {
vi v[2];
/*v[0].push_back(0);
v[use_machine({0,1})].push_back(1);
if(n==2)return v[0].size();
v[use_machine({0,2})].push_back(2);
if(n == 3)return v[0].size();
int i1,i2;*/
int ans = 0;
bool f;
int sq = min(n-1,320);
int m= 3;
for(int i = 3; i+k-2 < sq; i+=k-1){
vector<bitset<k>> b;
for(int j = 0; j < (1<<k); j+=2){
bitset<k> bb = j;
b.push_back(bb);
}
bitset<(1<<(k-1))>pos;for(int i = 0; i < 1<<(k-1); i++)pos[i]=1;
vi ind = {0}; for(int j = i; j < i+k-1; j++)ind.push_back(j);
while(pos.count()>1){
vi vec;
for(int j = 0; j < k; j++)if(rand()%2)vec.push_back(ind[j]);
int c = use_machine(vec);
for(int j = 0; j < (1<<(k-1)); j++){
int cc = 0;
for(int t= 0; t < vec.size()-1; t++){
cc+=b[j][vec[t]]^b[j][vec[t+1]];
}
if(cc!=c)pos[j]=0;
}
}
for(int j = 0; j < (1<<(k-1)); j++){
if(pos[j]){
for(int t= 1; t < k; t++){
v[(b[j][t])].push_back(ind[t]);
}
}
}
m = i+k-2;
}
ans = v[0].size();
f = (v[1].size() > v[0].size());
int s = v[f].size();
for(int i = m; i < n; i+=s){
int j = min(n-1, i+s-1);
vi q;
for(int k = i; k <= j; k++){
q.push_back(k);
q.push_back(v[f][k-i]);
}
int c = use_machine(q);
if(!f){
ans += q.size()/2;
ans -= (c/2);
ans -= (c%2);
}else{
ans += c/2;
ans+=c%2;
}
}
return ans;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 344 KB | Answer is not correct. |
| 2 | Halted | 0 ms | 0 KB | - |