제출 #75723

#제출 시각아이디문제언어결과실행 시간메모리
75723KieranHorgan자동 인형 (IOI18_doll)C++17
100 / 100
186 ms16792 KiB
#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; } int rev(int x, int n) { n = __builtin_ctz(n); int res = 0; for(int i = 0; i < n; i++) if(x & (1<<i)) res |= 1<<(n-1-i); // cerr << n << ": " << x << " -> " << res << endl; return res; } void buildTree(int curTrigger, int curSwitch) { globalCurSwitch = curSwitch; int x = AdjList[curTrigger].size(); int dummies = 0; while(__builtin_popcount(x+dummies) != 1) dummies++; vector<int> b = AdjList[curTrigger]; vector<int> a; int i, j; for(i = 0, j = 0; j < b.size() + dummies; j++) { if(i >= b.size() || rev(j, b.size()+dummies) < dummies) a.push_back(globalCurSwitch); else a.push_back(b[i++]); } // for(auto x: a) // cerr << x << " "; // cerr << endl; // for(auto x: b) // cerr << x << " "; // cerr << endl; // cerr << endl; vector<int> pos, posCop; 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(); for(int i = 1; i < A.size(); i++) AdjList[A[0]].push_back(A[i]); AdjList[A[0]].push_back(0); C.assign(M+1, -1); C[0] = A[0]; nextSwitch--; if(N == 1) C[1] = 0; else buildTree(A[0], C[A[0]]); 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); }

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'int recurseThroughTree(std::vector<int>)':
doll.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i = 0; i < b.size(); i+=2) {
      |                  ~~^~~~~~~~~~
doll.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   if(nextDummies == a.size()) {
      |      ~~~~~~~~~~~~^~~~~~~~~~~
doll.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 1; i < b.size(); i+=2) {
      |                  ~~^~~~~~~~~~
doll.cpp:38:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void buildTree(int, int)':
doll.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(i = 0, j = 0; j < b.size() + dummies; j++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
doll.cpp:67:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     if(i >= b.size() || rev(j, b.size()+dummies) < dummies) a.push_back(globalCurSwitch);
      |        ~~^~~~~~~~~~~
doll.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i = 0; i < b.size(); i+=2) {
      |                  ~~^~~~~~~~~~
doll.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int i = 1; i < b.size(); i+=2) {
      |                  ~~^~~~~~~~~~
doll.cpp:97:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   if(X.size() <= abs(curSwitch)-1) X.resize(abs(curSwitch)), Y.resize(abs(curSwitch));
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp:83:7: warning: variable 'nextDummies' set but not used [-Wunused-but-set-variable]
   83 |   int nextDummies = 0;
      |       ^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i = 1; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...