제출 #630758

#제출 시각아이디문제언어결과실행 시간메모리
630758jwvg0425죄수들의 도전 (IOI22_prison)C++17
80 / 100
13 ms1520 KiB
#include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> #include <bitset> #include <map> #include <set> #include <tuple> #include <string.h> #include <math.h> #include <random> #include <functional> #include <assert.h> #include <math.h> #define all(x) (x).begin(), (x).end() #define xx first #define yy second using namespace std; template<typename T, typename Pr = less<T>> using pq = priority_queue<T, vector<T>, Pr>; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; vector<int> bits[5005]; void makeBits(int l, int r) { int lx = l + 1, rx = r - 1; int m = (lx + rx) / 2; for (int i = l; i <= r; i++) { if (i == l) { bits[i].push_back(-1); continue; } if (i == r) { bits[i].push_back(-2); continue; } if (i <= m) bits[i].push_back(0); else bits[i].push_back(1); } if (lx <= m) makeBits(lx, m); if (m + 1 <= rx) makeBits(m + 1, rx); } int maxBit = 0; void process(vector<vector<int>>& res, int n, int turn, int bit) { if (bit == maxBit) return; res.push_back(vector<int>(n + 1, 0)); res.push_back(vector<int>(n + 1, 0)); res[bit * 2 - 1][0] = res[bit * 2][0] = turn; int me = -(turn + 1); int other = -((turn + 1) % 2 + 1); for (int i = 1; i <= n; i++) { if (bits[i].size() <= bit - 1) continue; for (int pre = 0; pre < 2; pre++) { if (bits[i][bit - 1] == -1) res[bit * 2 - 1 + pre][i] = me; else if (bits[i][bit - 1] == -2) res[bit * 2 - 1 + pre][i] = other; else if (bits[i][bit - 1] < pre) res[bit * 2 - 1 + pre][i] = me; else if (bits[i][bit - 1] > pre) res[bit * 2 - 1 + pre][i] = other; else { if (bits[i].size() <= bit) continue; if (bits[i][bit] == -1) res[bit * 2 - 1 + pre][i] = me; else if (bits[i][bit] == -2) res[bit * 2 - 1 + pre][i] = other; else res[bit * 2 - 1 + pre][i] = (bit + 1) * 2 - 1 + bits[i][bit]; } } } process(res, n, (turn + 1) % 2, bit + 1); } vector<vector<int>> devise_strategy(int N) { vector<vector<int>> res; makeBits(1, N); for (int i = 1; i <= N; i++) maxBit = max(maxBit, (int)bits[i].size()); res.push_back(vector<int>(N + 1, 0)); for (int i = 1; i <= N; i++) { if (bits[i][0] == -1) res[0][i] = -1; else if (bits[i][0] == 0) res[0][i] = 1; else if (bits[i][0] == 1) res[0][i] = 2; else res[0][i] = -2; } process(res, N, 1, 1); return res; }

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

prison.cpp: In function 'void process(std::vector<std::vector<int> >&, int, int, int)':
prison.cpp:79:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |   if (bits[i].size() <= bit - 1)
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~
prison.cpp:94:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     if (bits[i].size() <= bit)
      |         ~~~~~~~~~~~~~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...