Submission #698826

#TimeUsernameProblemLanguageResultExecution timeMemory
698826sharaelongKoala Game (APIO17_koala)C++17
100 / 100
59 ms440 KiB
#include "koala.h" #include <algorithm> #include <bits/stdc++.h> #include <ostream> #include <vector> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MAX_N = 100; int B[MAX_N], R[MAX_N]; int minValue(int N, int W) { // TODO: Implement Subtask 1 solution here. // You may leave this function unmodified if you are not attempting this // subtask. memset(B, 0, sizeof B); B[0] = 1; playRound(B, R); int zero_pos = find(R, R+N, 0) - R; return zero_pos; } int maxValue(int N, int W) { // TODO: Implement Subtask 2 solution here. // You may leave this function unmodified if you are not attempting this // subtask. for (int i=0; i<N; ++i) B[i] = 1; playRound(B, R); vector<int> half_large; for (int i=0; i<N; ++i) { if (R[i] == 2) half_large.push_back(i); } assert(half_large.size() == 50); memset(B, 0, sizeof B); for (int i: half_large) B[i] = 2; playRound(B, R); vector<int> quarter_large; for (int i=0; i<N; ++i) { if (R[i] == 3) quarter_large.push_back(i); } memset(B, 0, sizeof B); for (int i: quarter_large) B[i] = 4; playRound(B, R); vector<int> ninetyone_large; for (int i=0; i<N; ++i) { if (R[i] > 1) ninetyone_large.push_back(i); } memset(B, 0, sizeof B); for (int i: ninetyone_large) B[i] = 11; playRound(B, R); return find(R, R+N, 12) - R; } void sub3_helper(int x) { memset(B, 0, sizeof B); B[0] = B[1] = x; playRound(B, R); } int greaterValue(int N, int W) { // TODO: Implement Subtask 3 solution here. // You may leave this function unmodified if you are not attempting this // subtask. sub3_helper(4); if (R[0] == R[1]) { if (R[0] == 0) { sub3_helper(2); if (R[0] != R[1]) { // cout << "2 "; return R[0] < R[1]; } sub3_helper(1); // cout << "1 "; return R[0] < R[1]; } else { sub3_helper(8); // cout << "8 "; return R[0] < R[1]; } } else { // cout << "4 "; return R[0] < R[1]; } } void sub4_helper(int i, int j) { B[i] = B[j] = 100; playRound(B, R); B[i] = B[j] = 0; } void sub5_helper(int N, vector<int>& arr, int thres) { // cout << thres << ' '; // for (int x: arr) cout << x << ' '; // cout << endl; if (arr.size() == 1) return; if (arr.size() == 0) assert(false); memset(B, 0, sizeof B); for (int x: arr) B[x] = thres; playRound(B, R); vector<int> big, small; for (int i=0; i<N; ++i) { if (R[i] >= thres+1) big.push_back(i); } for (int x: arr) { if (find(big.begin(), big.end(), x) == big.end()) small.push_back(x); } if (small.size() == 0) { sub5_helper(N, big, thres+1); } else { sub5_helper(N, small, thres); sub5_helper(N, big, thres); } arr.clear(); for (int x: small) arr.push_back(x); for (int x: big) arr.push_back(x); } void allValues(int N, int W, int *P) { if (W == 2*N) { // TODO: Implement Subtask 4 solution here. // You may leave this block unmodified if you are not attempting this // subtask. vector<int> ord = { 0 }; for (int i=1; i<N; ++i) { int l = 0, r = i; // bar model while (l < r) { int mid = (l+r) / 2; sub4_helper(ord[mid], i); if (R[ord[mid]] < R[i]) { l = mid+1; } else { r = mid; } } vector<int> tmp; for (int i=0; i<l; ++i) tmp.push_back(ord[i]); tmp.push_back(i); for (int i=l; i<ord.size(); ++i) tmp.push_back(ord[i]); ord = tmp; } for (int i=0; i<N; ++i) P[ord[i]] = i+1; } else { // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. int min_pos = minValue(N, W); vector<vector<int>> q(8); // [1, 100] -> [1], [2, 50], [51, 100] fill(B, B+N, 1); playRound(B, R); for (int i=0; i<N; ++i) { if (R[i] >= 2) q[4].push_back(i); else q[0].push_back(i); } q[0].erase(find(q[0].begin(), q[0].end(), min_pos)); // [1, 50] -> [1, 25], [26, 50] memset(B, 0, sizeof B); for (int x: q[0]) B[x] = 1; playRound(B, R); for (int i=0; i<N; ++i) { if (R[i] >= 2) { q[2].push_back(i); auto it = find(q[0].begin(), q[0].end(), i); q[0].erase(it); } } // [2, 25] -> [2, 13], [14, 25] memset(B, 0, sizeof B); for (int x: q[0]) B[x] = 1; playRound(B, R); for (int i=0; i<N; ++i) { if (R[i] >= 2) { q[1].push_back(i); auto it = find(q[0].begin(), q[0].end(), i); q[0].erase(it); } } // [2, 13] -> [2, 7], [8, 13] vector<int> lq0, rq0; memset(B, 0, sizeof B); for (int x: q[0]) B[x] = 1; playRound(B, R); for (int i=0; i<N; ++i) { if (R[i] >= 2) rq0.push_back(i); } for (int x: q[0]) { if (find(rq0.begin(), rq0.end(), x) == rq0.end()) lq0.push_back(x); } // [26, 50] -> [26, 38], [39, 50] memset(B, 0, sizeof B); for (int x: q[1]) B[x] = 2; for (int x: q[2]) B[x] = 3; playRound(B, R); for (int i=0; i<N; ++i) { if (R[i] >= 4) { q[3].push_back(i); auto it = find(q[2].begin(), q[2].end(), i); q[2].erase(it); } } // [51, 100] -> [51, 75], [76, 100] memset(B, 0, sizeof B); for (int x: q[4]) B[x] = 2; playRound(B, R); for (int i=0; i<N; ++i) { if (R[i] >= 3) { q[6].push_back(i); auto it = find(q[4].begin(), q[4].end(), i); q[4].erase(it); } } // [51, 75] -> [51, 63], [64, 75] memset(B, 0, sizeof B); for (int x: q[0]) B[x] = 1; for (int x: q[1]) B[x] = 1; for (int x: q[4]) B[x] = 3; playRound(B, R); for (int i=0; i<N; ++i) { if (R[i] >= 4) { q[5].push_back(i); auto it = find(q[4].begin(), q[4].end(), i); q[4].erase(it); } } // [76, 100] -> [76, 88], [89, 100] memset(B, 0, sizeof B); for (int x: q[6]) B[x] = 3; playRound(B, R); for (int i=0; i<N; ++i) { if (R[i] >= 4) { q[7].push_back(i); auto it = find(q[6].begin(), q[6].end(), i); q[6].erase(it); } } sub5_helper(N, lq0, 2); sub5_helper(N, rq0, 3); sub5_helper(N, q[1], 4); for (int i=2; i<7; ++i) sub5_helper(N, q[i], 7); sub5_helper(N, q[7], 8); // for (int i=6; i<8; ++i) sub5_helper(N, q[i], 8); P[min_pos] = 1; for (int i=2; i<=7; ++i) P[lq0[i-2]] = i; for (int i=8; i<=13; ++i) P[rq0[i-8]] = i; for (int i=14; i<=25; ++i) P[q[1][i-14]] = i; for (int i=26; i<=38; ++i) P[q[2][i-26]] = i; for (int i=39; i<=50; ++i) P[q[3][i-39]] = i; for (int i=51; i<=63; ++i) P[q[4][i-51]] = i; for (int i=64; i<=75; ++i) P[q[5][i-64]] = i; for (int i=76; i<=88; ++i) P[q[6][i-76]] = i; for (int i=89; i<=100; ++i) P[q[7][i-89]] = i; // memset(B, 0, sizeof B); // for (int i=13; i<25; ++i) B[i] = 2; // for (int i=25; i<50; ++i) B[i] = 3; // playRound(B, R); // for (int i=0; i<N; ++i) cout << R[i] << ' '; // cout << endl; // cout << find(R, R+N, 4) - R << endl; } }

Compilation message (stderr)

koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:149:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             for (int i=l; i<ord.size(); ++i) tmp.push_back(ord[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...