Submission #106386

#TimeUsernameProblemLanguageResultExecution timeMemory
106386polyfish코알라 (APIO17_koala)C++14
61 / 100
65 ms532 KiB
#include "koala.h" #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "data" const int MAX_N = 202; int b[MAX_N], r[MAX_N], a[MAX_N]; pair<int, int> f[MAX_N][MAX_N]; int minValue(int N, int W) { // TODO: Implement Subtask 1 solution here. b[0] = 1; playRound(b, r); for (int i=0; i<N; ++i) { if (r[i]==0) return i; } return 0; } void trace(int n, int w, int& cnt) { if (w==0) return; if (f[n][w]==f[n-1][w]) return trace(n-1, w, cnt); cnt += (a[n]==*max_element(a+1, a+100+1)); trace(n-1, w-a[n]-1, cnt); } void test() { int n = 100, w = 100; // TODO: Implement Subtask 2 solution here. for (int i=1; i<=91; ++i) a[i] = 0; for (int i=92; i<=100; ++i) a[i] = 11; for (int i=1; i<=n; ++i) { for (int j=0; j<=w; ++j) { f[i][j] = f[i-1][j]; if (j>a[i]) f[i][j] = max(f[i][j], {f[i-1][j-a[i]-1].first + i, f[i-1][j-a[i]-1].second+1}); } } debug(f[n][w].first); debug(f[n][w].second); int cnt = 0; trace(n, w, cnt); debug(cnt); } int maxValue(int n, int w) { // TODO: Implement Subtask 2 solution here. // test(); vector<int> b0, b1, b2, b3; ///Round 1 for (int i=0; i<n; ++i) b[i] = 1; playRound(b, r); for (int i=0; i<n; ++i) { if (r[i]) b1.push_back(i); else b0.push_back(i); } ///Round 2 for (auto x : b0) b[x] = 0; for (auto x : b1) b[x] = 2; memset(r, 0, sizeof(r)); playRound(b, r); for (auto x : b1) { if (r[x]>=3) b2.push_back(x); } for (auto x : b2) b1.erase(find(b1.begin(), b1.end(), x)); ///Round 3 for (auto x : b0) b[x] = 0; for (auto x : b1) b[x] = 1; for (auto x : b2) b[x] = 3; memset(r, 0, sizeof(r)); playRound(b, r); for (auto x : b2) { if (r[x]>=4) b3.push_back(x); } for (auto x : b3) b2.erase(find(b2.begin(), b2.end(), x)); ///Round 4 memset(b, 0, sizeof(b)); for (auto x : b3) b[x] = 16; memset(r, 0, sizeof(r)); playRound(b, r); for (auto x : b3) { if (r[x]>=17) return x; } return 0; } int greaterValue(int n, int w) { // TODO: Implement Subtask 3 solution here. vector<int> cur; for (int i=0; i<n; ++i) cur.push_back(i); #define Find(v, x) find(v.begin(), v.end(), x)!=v.end() // for (int i=1; i<=13; ++i) { // memset(r, 0, sizeof(r)); // b[0] = b[1] = i; // playRound(b, r); // if (r[0]>i && r[1]<=i) // return 0; // if (r[0]<=i && r[1]>i) // return 1; // } int l = 1, h = 14; while (true) { int mid = (l + h) / 2; memset(r, 0, sizeof(r)); b[0] = b[1] = mid; playRound(b, r); if (r[0]==r[1] && r[1]==0) h = mid - 1; else if (r[0]==r[1] && r[1]>0) l = mid + 1; else if (r[0]<r[1]) return 1; else return 0; } #undef Find return 0; } 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. } else { // TODO: Implement Subtask 5 solution here. vector<int> p(n); for (int i=0; i<n; ++i) p[i] = i; sort(p.begin(), p.end(), [](int x, int y) { int l = 1, h = 14; while (true) { int mid = (l + h) / 2; memset(r, 0, sizeof(r)); memset(b, 0, sizeof(b)); b[x] = b[y] = mid; playRound(b, r); if (r[x]==r[y] && r[y]==0) h = mid - 1; else if (r[x]==r[y] && r[y]>0) l = mid + 1; else if (r[x]<r[y]) return true; else return false; } }); for (int i=0; i<n; ++i) P[p[i]] = i+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...