# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
75318 | 2018-09-09T08:25:00 Z | KieranHorgan | Mechanical Doll (IOI18_doll) | C++17 | 196 ms | 20704 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 recurseThroughTree(vector<int> b) { if(b.size() == 1) return b[0]; int curSwitch = nextSwitch--; vector<int> a; for(int i = 0; i < b.size(); i+=2) a.push_back(b[i]); int l = recurseThroughTree(a); a.clear(); 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; return curSwitch; } void buildTree(int curTrigger, int curSwitch) { int last = AdjList[curTrigger].back(); AdjList[curTrigger].pop_back(); while(__builtin_popcount(AdjList[curTrigger].size()+1) != 1) AdjList[curTrigger].push_back(curSwitch); AdjList[curTrigger].push_back(last); vector<int> a; for(int i = 0; i < AdjList[curTrigger].size(); i+=2) a.push_back(AdjList[curTrigger][i]); int l = recurseThroughTree(a); a.clear(); for(int i = 1; i < AdjList[curTrigger].size(); i+=2) a.push_back(AdjList[curTrigger][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; } int cnt[20]; int buildPerfect(vector<int> b) { if(b.size() == 1) return b[0]; int curSwitch = nextSwitch--; vector<int> a; for(int i = 0; i < b.size(); i+=2) a.push_back(b[i]); int l = recurseThroughTree(a); a.clear(); 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; return curSwitch; } void create_circuit(int M, vector<int> A_) { A = A_; int N = A.size(); if(N == 16) { C.assign(M+1, -1); C[0] = A[0]; A.erase(A.begin()); A.push_back(0); buildPerfect(A); } else { 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]); } } } 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 | 5 ms | 4940 KB | Output is correct |
2 | Correct | 45 ms | 8972 KB | Output is correct |
3 | Correct | 29 ms | 8508 KB | Output is correct |
4 | Correct | 5 ms | 4940 KB | Output is correct |
5 | Correct | 14 ms | 6092 KB | Output is correct |
6 | Correct | 45 ms | 10388 KB | Output is correct |
7 | 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 | 45 ms | 8972 KB | Output is correct |
3 | Correct | 29 ms | 8508 KB | Output is correct |
4 | Correct | 5 ms | 4940 KB | Output is correct |
5 | Correct | 14 ms | 6092 KB | Output is correct |
6 | Correct | 45 ms | 10388 KB | Output is correct |
7 | Correct | 4 ms | 4940 KB | Output is correct |
8 | Correct | 65 ms | 11044 KB | Output is correct |
9 | Correct | 66 ms | 11532 KB | Output is correct |
10 | Correct | 101 ms | 14084 KB | Output is correct |
11 | Correct | 4 ms | 4940 KB | Output is correct |
12 | Correct | 5 ms | 4940 KB | Output is correct |
13 | Correct | 7 ms | 4940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4940 KB | Output is correct |
2 | Correct | 45 ms | 8972 KB | Output is correct |
3 | Correct | 29 ms | 8508 KB | Output is correct |
4 | Correct | 5 ms | 4940 KB | Output is correct |
5 | Correct | 14 ms | 6092 KB | Output is correct |
6 | Correct | 45 ms | 10388 KB | Output is correct |
7 | Correct | 4 ms | 4940 KB | Output is correct |
8 | Correct | 65 ms | 11044 KB | Output is correct |
9 | Correct | 66 ms | 11532 KB | Output is correct |
10 | Correct | 101 ms | 14084 KB | Output is correct |
11 | Correct | 4 ms | 4940 KB | Output is correct |
12 | Correct | 5 ms | 4940 KB | Output is correct |
13 | Correct | 7 ms | 4940 KB | Output is correct |
14 | Correct | 142 ms | 15628 KB | Output is correct |
15 | Correct | 84 ms | 11080 KB | Output is correct |
16 | Correct | 168 ms | 13228 KB | Output is correct |
17 | Correct | 8 ms | 4900 KB | Output is correct |
18 | Correct | 4 ms | 4940 KB | Output is correct |
19 | Correct | 5 ms | 4940 KB | Output is correct |
20 | Correct | 117 ms | 14776 KB | Output is correct |
21 | Correct | 6 ms | 4940 KB | Output is correct |
22 | Correct | 4 ms | 4940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4940 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 | 4940 KB | Output is correct |
5 | Correct | 4 ms | 4940 KB | Output is correct |
6 | Correct | 4 ms | 4940 KB | Output is correct |
7 | Correct | 6 ms | 4940 KB | Output is correct |
8 | Correct | 4 ms | 4940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 5 ms | 4940 KB | Output is partially correct |
2 | Correct | 80 ms | 10892 KB | Output is correct |
3 | Partially correct | 136 ms | 15944 KB | Output is partially correct |
4 | Partially correct | 161 ms | 16460 KB | Output is partially correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 5 ms | 4940 KB | Output is partially correct |
2 | Correct | 80 ms | 10892 KB | Output is correct |
3 | Partially correct | 136 ms | 15944 KB | Output is partially correct |
4 | Partially correct | 161 ms | 16460 KB | Output is partially correct |
5 | Partially correct | 183 ms | 17856 KB | Output is partially correct |
6 | Partially correct | 179 ms | 18840 KB | Output is partially correct |
7 | Partially correct | 181 ms | 18504 KB | Output is partially correct |
8 | Partially correct | 196 ms | 19528 KB | Output is partially correct |
9 | Partially correct | 127 ms | 15220 KB | Output is partially correct |
10 | Partially correct | 192 ms | 20704 KB | Output is partially correct |
11 | Partially correct | 180 ms | 20296 KB | Output is partially correct |
12 | Partially correct | 121 ms | 15064 KB | Output is partially correct |
13 | Partially correct | 109 ms | 14024 KB | Output is partially correct |
14 | Partially correct | 113 ms | 13764 KB | Output is partially correct |
15 | Partially correct | 100 ms | 13292 KB | Output is partially correct |
16 | Partially correct | 7 ms | 5196 KB | Output is partially correct |
17 | Partially correct | 100 ms | 12744 KB | Output is partially correct |
18 | Partially correct | 100 ms | 12680 KB | Output is partially correct |
19 | Partially correct | 101 ms | 13548 KB | Output is partially correct |
20 | Partially correct | 135 ms | 15780 KB | Output is partially correct |
21 | Partially correct | 158 ms | 17912 KB | Output is partially correct |
22 | Partially correct | 125 ms | 14944 KB | Output is partially correct |