# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
75412 | 2018-09-09T15:36:44 Z | KieranHorgan | Mechanical Doll (IOI18_doll) | C++17 | 226 ms | 21100 KB |
#include "doll.h" #include <bits/stdc++.h> using namespace std; vector<int> A, X, Y, C; int dep[200]; int nextSwitch = -1; vector<int> AdjList[200005]; int globalCurSwitch; int recurseThroughTree(vector<int> b) { if(b.size() == 1) return b[0]; int curSwitch = nextSwitch--; vector<int> a; a.clear(); int nextDummies = 0; for(int i = 0; i < b.size(); i+=2) { if(b[i] == globalCurSwitch) nextDummies++; a.push_back(b[i]); } int l; if(nextDummies == a.size()) { l = globalCurSwitch; } else { l = recurseThroughTree(a); } a.clear(); for(int i = 1; i < b.size(); i+=2) { if(b[i] == globalCurSwitch) nextDummies++; a.push_back(b[i]); } int r = recurseThroughTree(a); if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch)); X[abs(curSwitch)-1] = l; Y[abs(curSwitch)-1] = r; return curSwitch; } bitset<200005> is; void buildTree(int curTrigger, int curSwitch) { globalCurSwitch = curSwitch; int x = AdjList[curTrigger].size(); int dummies = 0; while(__builtin_popcount(x+dummies) != 1) dummies++; // cerr << curTrigger << ": " << x+dummies << " " << dummies << endl; vector<int> b = AdjList[curTrigger]; vector<int> pos, posCop; if(pos.size() != dummies) pos = {0}; for(int i = x+dummies; i > 1; i /= 2) { if(pos.size() == dummies) break; posCop = pos; for(auto x: posCop) { pos.push_back(x+(i/2)); if(pos.size() == dummies) break; } // cerr << i << " " << pos.size() << endl; } is.reset(); for(auto x: pos) is[x]=1; pos.clear(); posCop.clear(); vector<int> a; for(int j = 0, i = 0; j < x+dummies; j++) { if(is[j]) a.push_back(globalCurSwitch); else a.push_back(b[i++]); } b = a; a.clear(); int nextDummies = 0; for(int i = 0; i < b.size(); i+=2) { a.push_back(b[i]); } int l = recurseThroughTree(a); a.clear(); nextDummies = 0; for(int i = 1; i < b.size(); i+=2) { a.push_back(b[i]); } int r = recurseThroughTree(a); a.clear(); if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch)); X[abs(curSwitch)-1] = l; Y[abs(curSwitch)-1] = r; } void create_circuit(int M, vector<int> A_) { A = A_; int N = A.size(); if(!A.empty()) { AdjList[0].push_back(A[0]); for(int i = 0; i+1 < A.size(); i++) { AdjList[A[i]].push_back(A[i+1]); } AdjList[A.back()].push_back(0); } C.assign(M+1, 0); for(int i = 0; i <= M; i++) { if(AdjList[i].empty()) { } else if(AdjList[i].size() == 1) { C[i] = AdjList[i][0]; } else { C[i] = nextSwitch--; buildTree(i, C[i]); // for(int j = C[i]; j > nextSwitch; j--) { // cerr << j << ": " << X[abs(j)-1] << " " << Y[abs(j)-1] << endl; // } } } double score; int S = X.size(); // cerr << S << " " << N+log2(N) << endl; if(S <= N + log2(N)) score = 1; else if(S <= 2*N) score = 0.5 + 0.4*((2*N - S)/(N-log2(N)))*((2*N - S)/(N-log2(N))); else score = 0; score *= 100; // cout << "Score: " << setprecision(7) << fixed << score << "\t"; answer(C, X, Y); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 35 ms | 8968 KB | Output is correct |
3 | Correct | 30 ms | 8524 KB | Output is correct |
4 | Correct | 5 ms | 4940 KB | Output is correct |
5 | Correct | 15 ms | 6092 KB | Output is correct |
6 | Correct | 46 ms | 10384 KB | Output is correct |
7 | Correct | 4 ms | 4940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 35 ms | 8968 KB | Output is correct |
3 | Correct | 30 ms | 8524 KB | Output is correct |
4 | Correct | 5 ms | 4940 KB | Output is correct |
5 | Correct | 15 ms | 6092 KB | Output is correct |
6 | Correct | 46 ms | 10384 KB | Output is correct |
7 | Correct | 4 ms | 4940 KB | Output is correct |
8 | Correct | 144 ms | 11124 KB | Output is correct |
9 | Correct | 134 ms | 11524 KB | Output is correct |
10 | Correct | 205 ms | 14180 KB | Output is correct |
11 | Correct | 4 ms | 4940 KB | Output is correct |
12 | Correct | 5 ms | 4940 KB | Output is correct |
13 | Correct | 4 ms | 4940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4940 KB | Output is correct |
2 | Correct | 35 ms | 8968 KB | Output is correct |
3 | Correct | 30 ms | 8524 KB | Output is correct |
4 | Correct | 5 ms | 4940 KB | Output is correct |
5 | Correct | 15 ms | 6092 KB | Output is correct |
6 | Correct | 46 ms | 10384 KB | Output is correct |
7 | Correct | 4 ms | 4940 KB | Output is correct |
8 | Correct | 144 ms | 11124 KB | Output is correct |
9 | Correct | 134 ms | 11524 KB | Output is correct |
10 | Correct | 205 ms | 14180 KB | Output is correct |
11 | Correct | 4 ms | 4940 KB | Output is correct |
12 | Correct | 5 ms | 4940 KB | Output is correct |
13 | Correct | 4 ms | 4940 KB | Output is correct |
14 | Correct | 226 ms | 15752 KB | Output is correct |
15 | Correct | 101 ms | 11120 KB | Output is correct |
16 | Correct | 155 ms | 13316 KB | Output is correct |
17 | Correct | 6 ms | 4940 KB | Output is correct |
18 | Correct | 4 ms | 4940 KB | Output is correct |
19 | Correct | 4 ms | 4940 KB | Output is correct |
20 | Correct | 191 ms | 14792 KB | Output is correct |
21 | Correct | 4 ms | 4940 KB | Output is correct |
22 | Correct | 4 ms | 4940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4988 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 4 ms | 4940 KB | Output is correct |
4 | Correct | 5 ms | 4972 KB | Output is correct |
5 | Correct | 4 ms | 4940 KB | Output is correct |
6 | Correct | 4 ms | 4940 KB | Output is correct |
7 | Correct | 4 ms | 4940 KB | Output is correct |
8 | Correct | 4 ms | 4940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4940 KB | Output is correct |
2 | Correct | 76 ms | 11044 KB | Output is correct |
3 | Runtime error | 85 ms | 21100 KB | Execution killed with signal 11 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4940 KB | Output is correct |
2 | Correct | 76 ms | 11044 KB | Output is correct |
3 | Runtime error | 85 ms | 21100 KB | Execution killed with signal 11 |
4 | Halted | 0 ms | 0 KB | - |