제출 #69332

#제출 시각아이디문제언어결과실행 시간메모리
69332E869120Unscrambling a Messy Bug (IOI16_messy)C++14
100 / 100
5 ms512 KiB
#include <vector> #include <string> #include <algorithm> using namespace std; #include "messy.h" // ------------------------------------------ 70 点解法 ------------------------------------- int N, B; string adds(vector<int>p) { string S; for (int i = 0; i < N; i++) S += "0"; for (int i = 0; i < p.size(); i++) S[p[i]] = '1'; return S; } void encode() { // --------------- Step 1. 0 から 6 を区別する for (int i = 0; i < B; i++) add_element(adds(vector<int>{i})); for (int i = 0; i < B - 1; i++) add_element(adds(vector<int>{i, i + 1})); add_element(adds(vector<int>{0, 1, 2})); for (int i = 0; i < B; i++) { for (int j = B; j < N; j++) { if ((j / (1 << i)) % 2 == 0) continue; vector<int>G; for (int k = 0; k < B; k++) { if (k != i) G.push_back(k); } G.push_back(j); add_element(adds(G)); } } } int p[128]; vector<int>X[7], P, ZZ; bool used[7]; void brute_force(int v, int mod, vector<int>V) { if (V.size() == 0) return; if (mod == 128) { p[V[0]] = v; return; } vector<int>V1, V2, W; for (int i = 0; i < B; i++) { if ((1 << i) != mod) W.push_back(ZZ[P[i]]); } for (int i = 0; i < V.size() - 1; i++) { vector<int>WW = W; WW.push_back(V[i]); if (check_element(adds(WW)) == false) V1.push_back(V[i]); else V2.push_back(V[i]); } int c1 = 0; for (int i = B; i < N; i++) { if (i % (mod * 2) == v) c1++; } if (c1 != V1.size()) V1.push_back(V[V.size() - 1]); else V2.push_back(V[V.size() - 1]); brute_force(v, mod * 2, V1); brute_force(v + mod, mod * 2, V2); } void decode() { vector<int>Z; for (int i = 0; i < N; i++) { if (check_element(adds(vector<int>{i})) == true) Z.push_back(i); } ZZ = Z; // Z は 7 個ある for (int i = 0; i < B; i++) { for (int j = i + 1; j < B; j++) { if (check_element(adds(vector<int>{Z[i], Z[j]})) == true) { X[i].push_back(j); X[j].push_back(i); } } } int cx = 0; for (int i = 0; i < B; i++) { if (X[i].size() == 1) cx = i; } for (int i = 0; i < B - 1; i++) { used[cx] = true; P.push_back(cx); for (int j = 0; j < X[cx].size(); j++) { if (used[X[cx][j]] == false) { cx = X[cx][j]; break; } } } P.push_back(cx); if (check_element(adds(vector<int>{Z[P[0]], Z[P[1]], Z[P[2]]})) == false) reverse(P.begin(), P.end()); for (int i = 0; i < B; i++) p[Z[P[i]]] = i; // ここからが本質 vector<int>E; for (int i = 0; i < N; i++) { bool OK = false; for (int j = 0; j < Z.size(); j++) { if (i == Z[j]) OK = true; } if (OK == false) E.push_back(i); } brute_force(0, 1, E); } bool uses[8]; void solve_2() { add_element(adds(vector<int>{0})); for (int i = 1; i < N; i++) add_element(adds(vector<int>{i - 1, i})); compile_set(); int cx = 0; p[cx] = 0; for (int i = 0; i < N; i++) { if (check_element(adds(vector<int>{i})) == true) cx = i; } int cnt = 0; while (true) { int px = -1; uses[cx] = true; for (int i = 0; i < N; i++) { if (uses[i] == false && check_element(adds(vector<int>{cx, i})) == true) px = i; } if (px == -1) break; cnt++; p[px] = cnt; cx = px; } } vector<int> restore_permutation(int n, int w, int r) { N = n; for (int i = 0; i <= 7; i++) { if ((1 << i) == n) B = i; } if (N == 4 || N == 8) { solve_2(); vector<int>vec; for (int i = 0; i < N; i++) vec.push_back(p[i]); return vec; } else { encode(); compile_set(); decode(); vector<int>Z; for (int i = 0; i < N; i++) Z.push_back(p[i]); return Z; } }

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

messy.cpp: In function 'std::__cxx11::string adds(std::vector<int>)':
messy.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++) S[p[i]] = '1';
                  ~~^~~~~~~~~~
messy.cpp: In function 'void brute_force(int, int, std::vector<int>)':
messy.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~
messy.cpp:47:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (c1 != V1.size()) V1.push_back(V[V.size() - 1]);
      ~~~^~~~~~~~~~~~
messy.cpp: In function 'void decode()':
messy.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < X[cx].size(); j++) { if (used[X[cx][j]] == false) { cx = X[cx][j]; break; } }
                   ~~^~~~~~~~~~~~~~
messy.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < Z.size(); j++) { if (i == Z[j]) OK = true; }
                   ~~^~~~~~~~~~
#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...