| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 879641 | 2023-11-27T19:16:03 Z | andrei_boaca | Mechanical Doll (IOI18_doll) | C++17 | 164 ms | 262144 KB |
#include "doll.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n;
const int INF=1e9;
vector<int> vecini[100005];
vector<int> C,X,Y;
vector<int> v;
int lft[5000005],rgt[5000005];
int s;
int state[5000005];
int added=0;
int build(int lg)
{
if(lg==1)
return INF;
added+=lg%2;
lg+=lg%2;
int a=build(lg/2);
int b=build(lg/2);
s++;
lft[s]=a;
rgt[s]=b;
return -s;
}
int plsmake()
{
if(v.size()==1)
return v[0];
ll lg=v.size();
added=0;
int c=build(lg);
vector<pii> ord;
for(int i=1;i<=lg+added;i++)
{
int nod=c;
while(true)
{
nod=abs(nod);
if(state[nod]==0)
{
if(lft[nod]==INF)
{
ord.push_back({nod,0});
state[nod]^=1;
break;
}
state[nod]=1;
nod=lft[nod];
continue;
}
else
{
if(rgt[nod]==INF)
{
ord.push_back({nod,1});
state[nod]^=1;
break;
}
state[nod]=0;
nod=rgt[nod];
continue;
}
}
}
for(int i=0;i<ord.size();i++)
{
int who=ord[i].first;
int dir=ord[i].second;
if(i+1<v.size())
{
if(dir==0)
lft[who]=v[i];
else
rgt[who]=v[i];
continue;
}
if(i+1==ord.size())
{
if(dir==0)
lft[who]=v.back();
else
rgt[who]=v.back();
continue;
}
if(dir==0)
lft[who]=c;
else
rgt[who]=c;
}
return c;
}
void create_circuit(int M, std::vector<int> A)
{
C.resize(M+1);
n=A.size();
if(n==16)
{
vector<int> v;
for(int i=1;i<A.size();i++)
v.push_back(A[i]);
v.push_back(0);
int c=plsmake();
for(int i=1;i<=M;i++)
C[i]=c;
for(int i=1;i<=s;i++)
{
X.push_back(lft[i]);
Y.push_back(rgt[i]);
}
answer(C,X,Y);
return;
}
for(int i=0;i<A.size();i++)
{
int x=A[i];
int nxt=0;
if(i+1<A.size())
nxt=A[i+1];
vecini[x].push_back(nxt);
}
C[0]=A[0];
for(int i=1;i<=M;i++)
{
if(vecini[i].empty())
{
C[i]=0;
continue;
}
else
{
v=vecini[i];
C[i]=plsmake();
}
}
for(int i=1;i<=s;i++)
{
X.push_back(lft[i]);
Y.push_back(rgt[i]);
}
/*for(int i=0;i<C.size();i++)
cout<<C[i]<<' ';
cout<<'\n';
for(int i=1;i<=s;i++)
cout<<-i<<' '<<X[i-1]<<' '<<Y[i-1]<<'\n';*/
answer(C,X,Y);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 3676 KB | Output is correct |
| 2 | Correct | 18 ms | 8028 KB | Output is correct |
| 3 | Correct | 14 ms | 7512 KB | Output is correct |
| 4 | Runtime error | 164 ms | 262144 KB | Execution killed with signal 9 |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 3676 KB | Output is correct |
| 2 | Correct | 18 ms | 8028 KB | Output is correct |
| 3 | Correct | 14 ms | 7512 KB | Output is correct |
| 4 | Runtime error | 164 ms | 262144 KB | Execution killed with signal 9 |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 3676 KB | Output is correct |
| 2 | Correct | 18 ms | 8028 KB | Output is correct |
| 3 | Correct | 14 ms | 7512 KB | Output is correct |
| 4 | Runtime error | 164 ms | 262144 KB | Execution killed with signal 9 |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 159 ms | 262144 KB | Execution killed with signal 9 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 1 ms | 5724 KB | Output is partially correct |
| 2 | Correct | 53 ms | 16088 KB | Output is correct |
| 3 | Partially correct | 101 ms | 22428 KB | Output is partially correct |
| 4 | Partially correct | 104 ms | 23028 KB | Output is partially correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 1 ms | 5724 KB | Output is partially correct |
| 2 | Correct | 53 ms | 16088 KB | Output is correct |
| 3 | Partially correct | 101 ms | 22428 KB | Output is partially correct |
| 4 | Partially correct | 104 ms | 23028 KB | Output is partially correct |
| 5 | Partially correct | 80 ms | 23572 KB | Output is partially correct |
| 6 | Partially correct | 85 ms | 27172 KB | Output is partially correct |
| 7 | Partially correct | 89 ms | 26572 KB | Output is partially correct |
| 8 | Partially correct | 85 ms | 27764 KB | Output is partially correct |
| 9 | Partially correct | 94 ms | 22044 KB | Output is partially correct |
| 10 | Partially correct | 122 ms | 29748 KB | Output is partially correct |
| 11 | Partially correct | 107 ms | 28348 KB | Output is partially correct |
| 12 | Partially correct | 65 ms | 20304 KB | Output is partially correct |
| 13 | Partially correct | 55 ms | 19220 KB | Output is partially correct |
| 14 | Partially correct | 54 ms | 18784 KB | Output is partially correct |
| 15 | Partially correct | 53 ms | 17948 KB | Output is partially correct |
| 16 | Partially correct | 3 ms | 6232 KB | Output is partially correct |
| 17 | Partially correct | 47 ms | 17492 KB | Output is partially correct |
| 18 | Partially correct | 56 ms | 17660 KB | Output is partially correct |
| 19 | Partially correct | 50 ms | 18276 KB | Output is partially correct |
| 20 | Partially correct | 66 ms | 21324 KB | Output is partially correct |
| 21 | Partially correct | 93 ms | 26076 KB | Output is partially correct |
| 22 | Partially correct | 65 ms | 20696 KB | Output is partially correct |