| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 839166 | 2023-08-28T22:29:33 Z | beaconmc | Mechanical Doll (IOI18_doll) | C++14 | 128 ms | 13492 KB |
#include "doll.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef int ll;
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
vector<ll> binorder(ll n){
if (n==0) return {0};
vector<ll> ans;
vector<ll> sus = binorder(n-1);
for (auto&i : sus){
ans.push_back(i*2);
}
for (auto&i : sus){
ans.push_back(i*2 + 1);
}
return ans;
}
void create_circuit(int M, vector<int> A) {
ll offset = 0;
ll N = A.size();
vector<ll> X;
vector<ll> Y;
vector<ll> ans;
ans.push_back(-1);
FOR(i, 1, M+1){
ans.push_back(-1);
}
FOR(i, 0, 30){
if (N < 2*(1<<i)){
ll diff = 2*(1<<i)-N ;
diff = (diff)/2;
FOR(j,1, (1<<(i))){
X.push_back(-j*2);
Y.push_back(-j*2-1);
}
FOR(j, (1<<(i)), (1<<(i+1)) - diff){
X.push_back(-1);
Y.push_back(-1);
}
set<ll> replace;
FOR(j, (1<<(i+1)) - diff, 1<<(i+1)){
replace.insert(j);
replace.insert(j-(1<<i));
}
vector<ll> order = binorder(i);
vector<ll> order2 = binorder(i);
for (auto&k : order2){
order.push_back(k + (1<<i));
}
vector<ll> stuff2(1<<(i+1));
FOR(j,0,order.size()){
stuff2[order[j]] = j;
}
vector<ll> stuff;
for (auto&j : stuff2){
if (!replace.count(j)) stuff.push_back(j);
}
FOR(j,0,N){
if (stuff[j] >= (1<<i)) Y[stuff[j]-1] = A[j];
else X[stuff[j]+(1<<i)-1] = A[j];
}
ll comb = -(X.size()+1);
ll final = -(X.size()+2);
FOR(j,0,X.size()){
if (X[j] <= -(1<<i) && replace.count(-X[j])) X[j] = comb;
}
FOR(j,0,Y.size()){
if (Y[j] == -(1<<(i+1))+1){
if (diff==1) Y[j] = comb;
else if (diff == 0) continue;
else Y[j] = final;
continue;
}
if (Y[j] <= -(1<<i) && replace.count(-Y[j])) Y[j] = comb;
}
if (diff == 1){
X.push_back(-1);
Y.push_back(-1);
}else if (diff >= 2){
X.push_back(-1);
Y.push_back(-1);
X.push_back(-1);
Y.push_back(0);
}
break;
}
}
Y[Y.size()-1] = 0;
// for (auto&i : ans){
// cout << i << " ";
// }cout << endl;
// for (auto&i : X){
// cout << i << " ";
// }cout << endl;
// for (auto&i : Y){
// cout << i << " ";
// }cout << endl;
answer(ans, X, Y);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 1 ms | 212 KB | Output is partially correct |
| 2 | Partially correct | 110 ms | 12856 KB | Output is partially correct |
| 3 | Partially correct | 114 ms | 13400 KB | Output is partially correct |
| 4 | Partially correct | 88 ms | 11192 KB | Output is partially correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 1 ms | 212 KB | Output is partially correct |
| 2 | Partially correct | 110 ms | 12856 KB | Output is partially correct |
| 3 | Partially correct | 114 ms | 13400 KB | Output is partially correct |
| 4 | Partially correct | 88 ms | 11192 KB | Output is partially correct |
| 5 | Partially correct | 97 ms | 11364 KB | Output is partially correct |
| 6 | Partially correct | 96 ms | 11192 KB | Output is partially correct |
| 7 | Partially correct | 91 ms | 11340 KB | Output is partially correct |
| 8 | Partially correct | 89 ms | 11280 KB | Output is partially correct |
| 9 | Partially correct | 108 ms | 13384 KB | Output is partially correct |
| 10 | Partially correct | 90 ms | 11248 KB | Output is partially correct |
| 11 | Partially correct | 92 ms | 11240 KB | Output is partially correct |
| 12 | Partially correct | 115 ms | 13452 KB | Output is partially correct |
| 13 | Partially correct | 128 ms | 12844 KB | Output is partially correct |
| 14 | Partially correct | 115 ms | 13372 KB | Output is partially correct |
| 15 | Partially correct | 108 ms | 13492 KB | Output is partially correct |
| 16 | Partially correct | 2 ms | 716 KB | Output is partially correct |
| 17 | Correct | 30 ms | 4696 KB | Output is correct |
| 18 | Partially correct | 119 ms | 12876 KB | Output is partially correct |
| 19 | Partially correct | 104 ms | 13280 KB | Output is partially correct |
| 20 | Partially correct | 88 ms | 11148 KB | Output is partially correct |
| 21 | Partially correct | 90 ms | 11236 KB | Output is partially correct |
| 22 | Partially correct | 89 ms | 11240 KB | Output is partially correct |