제출 #629771

#제출 시각아이디문제언어결과실행 시간메모리
629771spacewalker죄수들의 도전 (IOI22_prison)C++17
0 / 100
1 ms300 KiB
#include "prison.h" #include <vector> #include <bits/stdc++.h> using namespace std; constexpr int CHECK_A = 0, CHECK_B = 1, DECLARE_A_LESS = -1, DECLARE_B_LESS = -2; int layers(int N) { if (N < 3) return 1; else return 1 + layers(N / 3); } int getNthLSD(int N, int i) { if (i == 0) return N % 3; else return getNthLSD(N/3, i-1); } std::vector<std::vector<int>> devise_strategy(int N) { // we need 3 log3(N) + 1 states int L = layers(N-1); vector<vector<int>> ans(3 * layers(N-1) + 1, vector<int>(N+1)); // 0 move to {1, 2, 3} depending on A's L-1th ternary digit ans[0][0] = CHECK_A; for (int aval = 1; aval <= N; ++aval) ans[0][aval] = getNthLSD(aval-1, L-1) + 1; for (int layer = 1; 3 * layer <= ans.size(); ++layer) { // if odd layer, A's digit is written // if even layer, B's digit is written for (int state = 3 * layer - 2; state < 3 * layer; ++state) { ans[state][0] = (layer % 2 == 1 ? CHECK_B : CHECK_A); // check opposite number int storedDigit = (state - 1) % 3; for (int oval = 1; oval <= N; ++oval) { // other value int otherDigit = getNthLSD(oval-1, L-layer); if (storedDigit != otherDigit) { int storedLessOtherAns = DECLARE_A_LESS, storedGreaterOtherAns = DECLARE_B_LESS; // if it's actually B that's stored, interchange the two if (layer % 2 == 0) swap(storedLessOtherAns, storedGreaterOtherAns); if (storedDigit > otherDigit) ans[state][oval] = storedGreaterOtherAns; else ans[state][oval] = storedLessOtherAns; } else { // store the next digit and move states // the two numbers are equal. this shouldn't happen if (3 * layer + 1 == ans.size()) { ans[state][oval] = 0; } else { int digitToStore = getNthLSD(oval-1, L-layer-1); ans[state][oval] = digitToStore + 1 + 3 * layer; } } } } } return ans; }

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

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:26:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int layer = 1; 3 * layer <= ans.size(); ++layer) {
      |                         ~~~~~~~~~~^~~~~~~~~~~~~
prison.cpp:42:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                     if (3 * layer + 1 == ans.size()) {
      |                         ~~~~~~~~~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...