| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1078088 | 2024-08-27T12:33:49 Z | Faisal_Saqib | Rarest Insects (IOI22_insects) | C++17 | 1163 ms | 53368 KB |
#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
map<vector<int>,int> store;
vector<int> cur,real_;
void add(int i)
{
i--;
cur.push_back(i);
}
void rem(int i)
{
i--;
cur.pop_back();
}
void khatam()
{
cur.clear();
}
int ask()
{
if(store.find(cur)!=store.end())return store[cur];
for(auto&i:cur)
{
if(!binary_search(begin(real_),end(real_),i))
{
move_inside(i);
}
}
for(auto&j:real_)
{
if(!binary_search(begin(cur),end(cur),j))
{
move_outside(j);
}
}
real_=cur;
store[cur]=press_button();
// cout<<"asking \n";
// cout<<"For: ";
// for(auto i:cur)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// cout<<"Ans: "<<store[cur]<<endl;
return store[cur];
}
int min_cardinality(int n)
{
vector<int> heads={1};
add(1);
for(int i=2;i<=n;i++)
{
add(i);
if(ask()==1)
heads.push_back(i);
else
rem(i);
}
int sz=heads.size();
int s=1;
int e=n+1;
while(s+1<e)
{
int mid=(s+e)/2;
khatam();
int sm=0;
for(int i=1;i<=mid;i++)
add(i),sm++;
for(int j=mid+1;j<=n;j++)
{
add(j);
if(ask()>mid)
{
rem(j);
}
else{
sm++;
}
}
if(sm==((sz*mid)))
{
s=mid;
}
else{
e=mid;
}
}
return s;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Output is correct |
| 2 | Correct | 0 ms | 344 KB | Output is correct |
| 3 | Correct | 0 ms | 344 KB | Output is correct |
| 4 | Correct | 0 ms | 344 KB | Output is correct |
| 5 | Correct | 0 ms | 344 KB | Output is correct |
| 6 | Correct | 3 ms | 344 KB | Output is correct |
| 7 | Correct | 5 ms | 344 KB | Output is correct |
| 8 | Correct | 5 ms | 600 KB | Output is correct |
| 9 | Correct | 13 ms | 736 KB | Output is correct |
| 10 | Correct | 12 ms | 600 KB | Output is correct |
| 11 | Correct | 15 ms | 836 KB | Output is correct |
| 12 | Correct | 13 ms | 1372 KB | Output is correct |
| 13 | Correct | 12 ms | 600 KB | Output is correct |
| 14 | Correct | 12 ms | 808 KB | Output is correct |
| 15 | Correct | 9 ms | 600 KB | Output is correct |
| 16 | Correct | 11 ms | 828 KB | Output is correct |
| 17 | Correct | 8 ms | 600 KB | Output is correct |
| 18 | Correct | 12 ms | 604 KB | Output is correct |
| 19 | Correct | 14 ms | 1292 KB | Output is correct |
| 20 | Correct | 8 ms | 600 KB | Output is correct |
| 21 | Correct | 9 ms | 820 KB | Output is correct |
| 22 | Correct | 7 ms | 600 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Output is correct |
| 2 | Correct | 0 ms | 344 KB | Output is correct |
| 3 | Correct | 0 ms | 344 KB | Output is correct |
| 4 | Correct | 0 ms | 344 KB | Output is correct |
| 5 | Correct | 0 ms | 344 KB | Output is correct |
| 6 | Correct | 3 ms | 344 KB | Output is correct |
| 7 | Correct | 5 ms | 344 KB | Output is correct |
| 8 | Correct | 5 ms | 600 KB | Output is correct |
| 9 | Correct | 13 ms | 736 KB | Output is correct |
| 10 | Correct | 12 ms | 600 KB | Output is correct |
| 11 | Correct | 15 ms | 836 KB | Output is correct |
| 12 | Correct | 13 ms | 1372 KB | Output is correct |
| 13 | Correct | 12 ms | 600 KB | Output is correct |
| 14 | Correct | 12 ms | 808 KB | Output is correct |
| 15 | Correct | 9 ms | 600 KB | Output is correct |
| 16 | Correct | 11 ms | 828 KB | Output is correct |
| 17 | Correct | 8 ms | 600 KB | Output is correct |
| 18 | Correct | 12 ms | 604 KB | Output is correct |
| 19 | Correct | 14 ms | 1292 KB | Output is correct |
| 20 | Correct | 8 ms | 600 KB | Output is correct |
| 21 | Correct | 9 ms | 820 KB | Output is correct |
| 22 | Correct | 7 ms | 600 KB | Output is correct |
| 23 | Correct | 45 ms | 3408 KB | Output is correct |
| 24 | Correct | 82 ms | 2896 KB | Output is correct |
| 25 | Correct | 81 ms | 2640 KB | Output is correct |
| 26 | Correct | 212 ms | 11036 KB | Output is correct |
| 27 | Correct | 86 ms | 4196 KB | Output is correct |
| 28 | Correct | 254 ms | 12704 KB | Output is correct |
| 29 | Correct | 137 ms | 6092 KB | Output is correct |
| 30 | Correct | 135 ms | 5916 KB | Output is correct |
| 31 | Correct | 196 ms | 7936 KB | Output is correct |
| 32 | Correct | 186 ms | 8940 KB | Output is correct |
| 33 | Correct | 202 ms | 9692 KB | Output is correct |
| 34 | Correct | 166 ms | 7492 KB | Output is correct |
| 35 | Correct | 228 ms | 9396 KB | Output is correct |
| 36 | Correct | 188 ms | 9356 KB | Output is correct |
| 37 | Correct | 236 ms | 10112 KB | Output is correct |
| 38 | Correct | 172 ms | 7852 KB | Output is correct |
| 39 | Correct | 141 ms | 7240 KB | Output is correct |
| 40 | Correct | 141 ms | 6768 KB | Output is correct |
| 41 | Correct | 144 ms | 6988 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Output is correct |
| 2 | Correct | 0 ms | 344 KB | Output is correct |
| 3 | Correct | 0 ms | 344 KB | Output is correct |
| 4 | Correct | 1 ms | 344 KB | Output is correct |
| 5 | Correct | 0 ms | 344 KB | Output is correct |
| 6 | Correct | 1 ms | 436 KB | Output is correct |
| 7 | Correct | 205 ms | 11100 KB | Output is correct |
| 8 | Correct | 452 ms | 10232 KB | Output is correct |
| 9 | Partially correct | 745 ms | 21604 KB | Output is partially correct |
| 10 | Partially correct | 982 ms | 41120 KB | Output is partially correct |
| 11 | Partially correct | 281 ms | 13068 KB | Output is partially correct |
| 12 | Partially correct | 929 ms | 53368 KB | Output is partially correct |
| 13 | Partially correct | 522 ms | 21492 KB | Output is partially correct |
| 14 | Partially correct | 603 ms | 23484 KB | Output is partially correct |
| 15 | Partially correct | 824 ms | 24164 KB | Output is partially correct |
| 16 | Partially correct | 1026 ms | 34720 KB | Output is partially correct |
| 17 | Partially correct | 891 ms | 29028 KB | Output is partially correct |
| 18 | Partially correct | 1062 ms | 33432 KB | Output is partially correct |
| 19 | Partially correct | 995 ms | 36728 KB | Output is partially correct |
| 20 | Partially correct | 1058 ms | 36120 KB | Output is partially correct |
| 21 | Partially correct | 956 ms | 40364 KB | Output is partially correct |
| 22 | Partially correct | 890 ms | 37720 KB | Output is partially correct |
| 23 | Partially correct | 718 ms | 27292 KB | Output is partially correct |
| 24 | Partially correct | 765 ms | 29492 KB | Output is partially correct |
| 25 | Partially correct | 765 ms | 26708 KB | Output is partially correct |
| 26 | Partially correct | 869 ms | 27764 KB | Output is partially correct |
| 27 | Partially correct | 475 ms | 10272 KB | Output is partially correct |
| 28 | Partially correct | 559 ms | 17352 KB | Output is partially correct |
| 29 | Partially correct | 576 ms | 11792 KB | Output is partially correct |
| 30 | Partially correct | 539 ms | 12544 KB | Output is partially correct |
| 31 | Partially correct | 816 ms | 28752 KB | Output is partially correct |
| 32 | Partially correct | 887 ms | 35788 KB | Output is partially correct |
| 33 | Partially correct | 692 ms | 21384 KB | Output is partially correct |
| 34 | Partially correct | 593 ms | 21508 KB | Output is partially correct |
| 35 | Partially correct | 484 ms | 11504 KB | Output is partially correct |
| 36 | Partially correct | 701 ms | 17800 KB | Output is partially correct |
| 37 | Partially correct | 712 ms | 29064 KB | Output is partially correct |
| 38 | Partially correct | 739 ms | 28736 KB | Output is partially correct |
| 39 | Partially correct | 494 ms | 10308 KB | Output is partially correct |
| 40 | Partially correct | 488 ms | 10332 KB | Output is partially correct |
| 41 | Partially correct | 552 ms | 12824 KB | Output is partially correct |
| 42 | Partially correct | 531 ms | 10728 KB | Output is partially correct |
| 43 | Partially correct | 48 ms | 2668 KB | Output is partially correct |
| 44 | Partially correct | 386 ms | 16476 KB | Output is partially correct |
| 45 | Partially correct | 655 ms | 18884 KB | Output is partially correct |
| 46 | Partially correct | 605 ms | 34484 KB | Output is partially correct |
| 47 | Partially correct | 1163 ms | 47548 KB | Output is partially correct |
| 48 | Partially correct | 854 ms | 51296 KB | Output is partially correct |