제출 #392561

#제출 시각아이디문제언어결과실행 시간메모리
392561JimmyZJX자동 인형 (IOI18_doll)C++14
47 / 100
206 ms14068 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <unordered_set> #include <unordered_map> using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define forR(i, n) for (int i = 0; i < (n); i++) void answer(Vi C, Vi X, Vi Y); Vi C, X, Y; Vi swState; int getLevelSW(int sz) { int level = 1, maxSz = 2; while (sz > maxSz) { level++, maxSz *= 2; } return level; } int getSW(int root = 0) { int swNo = -1 - X.size(); X.push_back(root); Y.push_back(root); swState.push_back(0); return swNo; } void setSWX(int sw, int t) { X[-1 - sw] = t; } void setSWY(int sw, int t) { Y[-1 - sw] = t; } int getStateSW(int sw) { int state = swState[sw]; swState[sw] = 1 - state; return state; } int& goAlong(int node, int step) { int* nodePtr = NULL; for (int i = 0; i < step; i++) { assert(node < 0); int sw = -1 - node; if (getStateSW(sw) == 0) { nodePtr = &X[sw]; } else { nodePtr = &Y[sw]; } node = *nodePtr; } return *nodePtr; } int buildLevelSW(int lvl) { int root = getSW(); Vi sws(1, root); for (int i = 1; i < lvl; i++) { Vi sw_lvl; for (int sw : sws) { int sw0 = getSW(root), sw1 = getSW(root); sw_lvl.push_back(sw0); sw_lvl.push_back(sw1); setSWX(sw, sw0); setSWY(sw, sw1); } sws = sw_lvl; } return root; } void build_answer(int node, const Vi& nexts) { if (nexts.size() == 0) { C[node] = 0; return; } else if (nexts.size() == 1) { C[node] = nexts[0]; return; } int lvlSW = getLevelSW(nexts.size()); int numSW = (1 << lvlSW) - 1; int root = buildLevelSW(lvlSW); forR(i, ((1 << lvlSW) - nexts.size())) { goAlong(root, lvlSW) = root; } for (int next : nexts) { goAlong(root, lvlSW) = next; } C[node] = root; } void create_circuit(int M, Vi A) { int n = A.size(); X = Y = swState = Vi(); C = Vi(M + 1); C[0] = A[0]; Vii nexts(M + 1); A.push_back(0); forR(i, n) { nexts[A[i]].push_back(A[i + 1]); } int lvl = getLevelSW(n); int root = buildLevelSW(lvl); int skips = (1 << lvl) - n; forR(i, skips) { goAlong(root, lvl) = root; } forR(i, n) { goAlong(root, lvl) = A[i + 1]; } forR(i, M) C[i + 1] = root; //forR(i, M) { // build_answer(i + 1, nexts[i + 1]); //} answer(C, X, Y); }

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

doll.cpp: In function 'void build_answer(int, const Vi&)':
doll.cpp:24:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | #define forR(i, n) for (int i = 0; i < (n); i++)
      |                                      ^
doll.cpp:104:2: note: in expansion of macro 'forR'
  104 |  forR(i, ((1 << lvlSW) - nexts.size())) {
      |  ^~~~
doll.cpp:101:6: warning: unused variable 'numSW' [-Wunused-variable]
  101 |  int numSW = (1 << lvlSW) - 1;
      |      ^~~~~
#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...