| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 790647 | 2023-07-23T04:07:33 Z | Amylopectin | The Big Prize (IOI17_prize) | C++14 | 61 ms | 24068 KB |
#include "prize.h"
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 1e6 + 10;
vector<int> ret[mxn] = {};
int ans = -1,cal = -1,tot;
int fii(int cl,int cr,int lea,int ria)
{
int i,j,mid = (cl+cr) / 2,lva,rva,cou = 0,cru;
if(ret[mid].size() == 0)
{
ret[mid] = ask(mid);
}
lva = ret[mid][0];
rva = ret[mid][1];
cru = mid;
if(lva + rva > tot)
{
tot = lva + rva;
cal = 1;
return 0;
}
if(lva + rva == 0)
{
ans = cru;
return 0;
}
while(lva + rva < tot)
{
if(lva + rva == 0)
{
ans = cru;
return 0;
}
cou ++;
cru ++;
if(cru > cr)
{
break;
}
if(ret[cru].size() == 0)
{
ret[cru] = ask(cru);
}
lva = ret[cru][0];
rva = ret[cru][1];
if(lva + rva > tot)
{
tot = lva + rva;
cal = 1;
return 0;
}
}
if(cru <= cr)
{
lva -= cou;
if(lva - lea > 0 && mid > cl)
{
fii(cl,mid-1,lea,rva + cou);
if(ans != -1|| cal == 1)
{
return 0;
}
}
if(rva - ria > 0 && cru < cr)
{
fii(cru+1,cr,lva + cou,ria);
if(ans != -1|| cal == 1)
{
return 0;
}
}
}
else
{
cru = mid-1;
if(ret[cru].size() == 0)
{
ret[cru] = ask(cru);
}
lva = ret[cru][0];
rva = ret[cru][1];
if(lva + rva > tot)
{
tot = lva + rva;
cal = 1;
return 0;
}
if(lva + rva == 0)
{
ans = cru;
return 0;
}
while(lva + rva < tot)
{
if(lva + rva == 0)
{
ans = cru;
return 0;
}
cou ++;
cru --;
if(cru < cl)
{
break;
}
if(ret[cru].size() == 0)
{
ret[cru] = ask(cru);
}
lva = ret[cru][0];
rva = ret[cru][1];
if(lva + rva > tot)
{
tot = lva + rva;
cal = 1;
return 0;
}
}
if(cru < cl)
{
return 0;
}
if(lva - lea > 0 && cru > cl)
{
fii(cl,cru-1,lea,rva);
if(ans != -1 || cal == 1)
{
return 0;
}
}
}
return 0;
}
int find_best(int n)
{
int i,j,cn,cm,fn,fm,mid = (n-1)/2;
tot = -1;
ret[mid] = ask(mid);
tot = ret[mid][0] + ret[mid][1];
while(1)
{
cal = -1;
ans = -1;
fii(0,n-1,0,0);
if(cal == -1)
{
break;
}
}
// for(int i = 0; i < n; i++)
// {
// std::vector<int> res = ask(i);
// if(res[0] + res[1] == 0)
// return i;
// }
return ans;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 23760 KB | Output is correct |
| 2 | Correct | 16 ms | 23760 KB | Output is correct |
| 3 | Correct | 16 ms | 23656 KB | Output is correct |
| 4 | Correct | 13 ms | 23760 KB | Output is correct |
| 5 | Correct | 13 ms | 23760 KB | Output is correct |
| 6 | Correct | 13 ms | 23784 KB | Output is correct |
| 7 | Correct | 14 ms | 23672 KB | Output is correct |
| 8 | Correct | 13 ms | 23760 KB | Output is correct |
| 9 | Correct | 13 ms | 23776 KB | Output is correct |
| 10 | Correct | 14 ms | 23760 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 23684 KB | Output is correct |
| 2 | Correct | 14 ms | 23760 KB | Output is correct |
| 3 | Correct | 12 ms | 23724 KB | Output is correct |
| 4 | Correct | 12 ms | 23760 KB | Output is correct |
| 5 | Correct | 16 ms | 23760 KB | Output is correct |
| 6 | Correct | 16 ms | 23728 KB | Output is correct |
| 7 | Correct | 13 ms | 23776 KB | Output is correct |
| 8 | Correct | 12 ms | 23692 KB | Output is correct |
| 9 | Correct | 16 ms | 23780 KB | Output is correct |
| 10 | Correct | 13 ms | 23760 KB | Output is correct |
| 11 | Correct | 17 ms | 23760 KB | Output is correct |
| 12 | Correct | 13 ms | 23776 KB | Output is correct |
| 13 | Correct | 14 ms | 23800 KB | Output is correct |
| 14 | Correct | 13 ms | 23724 KB | Output is correct |
| 15 | Correct | 17 ms | 23792 KB | Output is correct |
| 16 | Correct | 26 ms | 23876 KB | Output is correct |
| 17 | Correct | 15 ms | 23660 KB | Output is correct |
| 18 | Correct | 45 ms | 23900 KB | Output is correct |
| 19 | Correct | 16 ms | 23764 KB | Output is correct |
| 20 | Correct | 23 ms | 23760 KB | Output is correct |
| 21 | Correct | 19 ms | 23928 KB | Output is correct |
| 22 | Correct | 17 ms | 23760 KB | Output is correct |
| 23 | Correct | 14 ms | 23784 KB | Output is correct |
| 24 | Correct | 13 ms | 23780 KB | Output is correct |
| 25 | Correct | 36 ms | 23928 KB | Output is correct |
| 26 | Correct | 33 ms | 23812 KB | Output is correct |
| 27 | Correct | 16 ms | 23752 KB | Output is correct |
| 28 | Correct | 35 ms | 23848 KB | Output is correct |
| 29 | Correct | 32 ms | 23780 KB | Output is correct |
| 30 | Correct | 31 ms | 24020 KB | Output is correct |
| 31 | Correct | 13 ms | 23780 KB | Output is correct |
| 32 | Correct | 15 ms | 23804 KB | Output is correct |
| 33 | Correct | 12 ms | 23720 KB | Output is correct |
| 34 | Correct | 20 ms | 23808 KB | Output is correct |
| 35 | Correct | 17 ms | 23760 KB | Output is correct |
| 36 | Correct | 21 ms | 23784 KB | Output is correct |
| 37 | Correct | 14 ms | 23896 KB | Output is correct |
| 38 | Correct | 16 ms | 23684 KB | Output is correct |
| 39 | Correct | 32 ms | 23792 KB | Output is correct |
| 40 | Correct | 51 ms | 23788 KB | Output is correct |
| 41 | Correct | 36 ms | 23812 KB | Output is correct |
| 42 | Correct | 23 ms | 23964 KB | Output is correct |
| 43 | Correct | 32 ms | 23924 KB | Output is correct |
| 44 | Correct | 25 ms | 23764 KB | Output is correct |
| 45 | Correct | 21 ms | 23772 KB | Output is correct |
| 46 | Correct | 17 ms | 23696 KB | Output is correct |
| 47 | Correct | 24 ms | 23800 KB | Output is correct |
| 48 | Correct | 32 ms | 23948 KB | Output is correct |
| 49 | Correct | 15 ms | 23776 KB | Output is correct |
| 50 | Correct | 36 ms | 23832 KB | Output is correct |
| 51 | Correct | 34 ms | 23780 KB | Output is correct |
| 52 | Correct | 15 ms | 23784 KB | Output is correct |
| 53 | Correct | 14 ms | 23780 KB | Output is correct |
| 54 | Correct | 28 ms | 23760 KB | Output is correct |
| 55 | Correct | 13 ms | 23760 KB | Output is correct |
| 56 | Correct | 51 ms | 23864 KB | Output is correct |
| 57 | Correct | 39 ms | 23796 KB | Output is correct |
| 58 | Correct | 29 ms | 23760 KB | Output is correct |
| 59 | Correct | 36 ms | 23828 KB | Output is correct |
| 60 | Correct | 24 ms | 23868 KB | Output is correct |
| 61 | Correct | 14 ms | 23760 KB | Output is correct |
| 62 | Correct | 14 ms | 23716 KB | Output is correct |
| 63 | Correct | 14 ms | 23788 KB | Output is correct |
| 64 | Correct | 16 ms | 23812 KB | Output is correct |
| 65 | Correct | 14 ms | 23760 KB | Output is correct |
| 66 | Correct | 28 ms | 23748 KB | Output is correct |
| 67 | Correct | 17 ms | 23776 KB | Output is correct |
| 68 | Correct | 16 ms | 23784 KB | Output is correct |
| 69 | Correct | 20 ms | 23784 KB | Output is correct |
| 70 | Correct | 14 ms | 23804 KB | Output is correct |
| 71 | Correct | 53 ms | 23880 KB | Output is correct |
| 72 | Correct | 18 ms | 23788 KB | Output is correct |
| 73 | Correct | 61 ms | 23932 KB | Output is correct |
| 74 | Correct | 48 ms | 23808 KB | Output is correct |
| 75 | Correct | 15 ms | 23760 KB | Output is correct |
| 76 | Correct | 30 ms | 23892 KB | Output is correct |
| 77 | Correct | 51 ms | 23876 KB | Output is correct |
| 78 | Correct | 19 ms | 23792 KB | Output is correct |
| 79 | Correct | 28 ms | 23816 KB | Output is correct |
| 80 | Correct | 55 ms | 23836 KB | Output is correct |
| 81 | Correct | 41 ms | 23836 KB | Output is correct |
| 82 | Correct | 29 ms | 23788 KB | Output is correct |
| 83 | Correct | 14 ms | 23788 KB | Output is correct |
| 84 | Correct | 35 ms | 24068 KB | Output is correct |
| 85 | Correct | 47 ms | 23904 KB | Output is correct |
| 86 | Correct | 17 ms | 23792 KB | Output is correct |
| 87 | Correct | 13 ms | 23760 KB | Output is correct |
| 88 | Correct | 18 ms | 23768 KB | Output is correct |
| 89 | Correct | 17 ms | 23752 KB | Output is correct |
| 90 | Correct | 14 ms | 23760 KB | Output is correct |
| 91 | Correct | 19 ms | 23784 KB | Output is correct |
| 92 | Correct | 19 ms | 23760 KB | Output is correct |
| 93 | Correct | 16 ms | 23784 KB | Output is correct |
| 94 | Correct | 29 ms | 23692 KB | Output is correct |
| 95 | Correct | 13 ms | 23760 KB | Output is correct |
| 96 | Correct | 18 ms | 23712 KB | Output is correct |
| 97 | Correct | 14 ms | 23676 KB | Output is correct |