| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 299733 | Dremix10 | Mechanical Doll (IOI18_doll) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
void create_circuit(int m, vector<int> a) {
int n = a.size();
/// each trigger can only go to one place
/// so in the case of {1,2,1} 1 can't go to 2 because
/// the second time we get to 1 we will go to 2 which
/// shouldn't happen
int i,s = 1;
vector<int> ans(m+1);
vector<int> x,y;
int cnt[m+1]={};
for(auto x : a)
cnt[x]++;
int now[m+1]={};
ans[0] = a[0];
a.push_back(0);
/// build circuit /*
for(i=0;i<n;i++){
int curr = a[i];
if(cnt[curr]==1){
ans[curr] = a[i+1];
}
else if(cnt[curr]==2){
if(!now[curr]){
ans[curr] = -s;
s++;
x.push_back(a[i+1]);
y.push_back(-1);
now[curr]++;
}
else{
y[-ans[curr]-1] = a[i+1];
now[curr]++;
}
}
else if(cnt[curr]==3){
if(!now[curr]){
ans[curr] = -s;
/// creating and directing first switch
s++;
x.push_back(-s);
s++;
y.push_back(-s);
s++;
/// configure second switch
x.push_back(a[i+1]);
y.push_back(ans[curr]);
/// prep third switch
x.push_back(-1);
y.push_back(-1);
now[curr]++;
}
else if(now[curr]==1){
int idx = y[-ans[curr]-1];
/// configure half third switch
x[-idx-1] = a[i+1];
now[curr]++;
}
else{
int idx = y[-ans[curr]-1];
/// configure other half third switch
y[-idx-1] = a[i+1];
now[curr]++;
}
}
else{
if(!now[curr]){
ans[curr] = -s;
/// creating and directing first switch
s++;
x.push_back(-s);
s++;
y.push_back(-s);
s++;
/// configure half second switch + prep other
x.push_back(a[i+1]);
y.push_back(-1);
/// prep third switch
x.push_back(-1);
y.push_back(-1);
now[curr]++;
}
else if(now[curr]==1){
int idx = y[-ans[curr]-1];
/// configure half third switch
x[-idx-1] = a[i+1];
now[curr]++;
}
else if(now[curr]==2){
int idx = x[-ans[curr]-1];
/// configure other half second switch
y[-idx-1] = a[i+1];
now[curr]++;
}
else{
int idx = y[-ans[curr]-1];
/// configure other half third switch
y[-idx-1] = a[i+1];
now[curr]++;
}
}
}
/// build circuit */
for(i=1;i<=m;i++)
if(!cnt[i])ans[i] = i;
answer(ans,x,y);
}