Submission #70588

#TimeUsernameProblemLanguageResultExecution timeMemory
70588funcsrKoala Game (APIO17_koala)C++17
100 / 100
570 ms4060 KiB
#include "koala.h" #include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <queue> #include <set> #include <map> #include <cmath> #include <iomanip> #include <cassert> #include <bitset> using namespace std; typedef pair<int, int> P; #define rep(i, n) for (int i=0; i<(n); i++) #define all(c) (c).begin(), (c).end() #define uniq(c) c.erase(unique(all(c)), (c).end()) #define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin()) #define _1 first #define _2 second #define pb push_back #define INF 1145141919 #define MOD 1000000007 int N, W; tuple<int,int,int> dp[201]; int simulation(vector<int> cost, int l, int r) { rep(i, W+1) dp[i] = make_tuple(0, 0, 0); rep(i, N) { assert(cost[i] > 0); for (int j=W-cost[i]; j>=0; j--) { dp[j+cost[i]] = max(dp[j+cost[i]], make_tuple(get<0>(dp[j])+(i+1), get<1>(dp[j])+1, get<2>(dp[j])-(l<=i+1&&i+1<=r))); } } return -get<2>(dp[W]); } int perm[100]; void solve(int l, int r, vector<int> set) { assert(r-l+1 == set.size()); assert(l<=r); //cout<<"["<<l<<","<<r<<"] {";for(int x: set)cout<<x<<",";cout<<"}\n"; if (l == r) { perm[set[0]] = l; return; } pair<int, P> mp = make_pair(INF, P(-1, -1)); for (int outside=1; outside<=100; outside++) { for (int k=2; k<=100; k++) { if ((outside-1)*(N-(r-l+1)) + (k-1)*(r-l+1) > W) break; vector<int> cost(N); for (int i=1; i<=N; i++) { if (l <= i && i <= r) cost[i-1] = k; else cost[i-1] = outside; } int left = simulation(cost, l, r); int right = (r-l+1)-left; if (left==0||right==0)continue; mp = min(mp, make_pair(abs(left-right), P(k, outside))); if (mp._1 <= 1) break; } if (mp._1 <= 1) break; } int val = mp._2._1; int outside = mp._2._2; //cout<<"val="<<val<<", outside="<<outside<<": "<<mp._1<<"\n"; assert(val!=-1); int B[100], R[100]; rep(i, N) B[i] = outside-1; for (int i : set) B[i] = val-1; playRound(B, R); vector<int> left, right; for (int i : set) { if (R[i] >= val) right.pb(i); else left.pb(i); } solve(l, l+left.size()-1, left); solve(l+left.size(), r, right); } int solve2(int l, int r, vector<int> set) { assert(r-l+1 == set.size()); assert(l<=r); //cout<<"["<<l<<","<<r<<"] {";for(int x: set)cout<<x<<",";cout<<"}\n"; if (l == r) return set[0]; pair<int, P> mp = make_pair(INF, P(-1, -1)); for (int outside=1; outside<=100; outside++) { for (int k=2; k<=100; k++) { if ((outside-1)*(N-(r-l+1)) + (k-1)*(r-l+1) > W) break; vector<int> cost(N); for (int i=1; i<=N; i++) { if (l <= i && i <= r) cost[i-1] = k; else cost[i-1] = outside; } int right = simulation(cost, l, r); int left = (r-l+1)-right; if (right==0) continue; mp = min(mp, make_pair(right, P(k, outside))); if (mp._1 <= 1) break; } if (mp._1 <= 1) break; } int val = mp._2._1; int outside = mp._2._2; //cout<<"val="<<val<<", outside="<<outside<<": "<<mp._1<<"\n"; assert(val!=-1); int B[100], R[100]; rep(i, N) B[i] = outside-1; for (int i : set) B[i] = val-1; playRound(B, R); vector<int> left, right; for (int i : set) { if (R[i] >= val) right.pb(i); else left.pb(i); } return solve2(l+left.size(), r, right); } int minValue(int N, int W) { int B[N], R[N]; rep(i, N) B[i] = 0; B[0] = 1; playRound(B, R); rep(i, N) if (R[i] <= B[i]) return i; abort(); } int maxValue(int NN, int WW) { N = NN, W = WW; vector<int> left, right; vector<int> all; rep(i, N) all.pb(i); return solve2(1, N, all); } int cmp(int w) { int B[N], R[N]; rep(i, N) B[i] = 0; B[0] = w; B[1] = w; playRound(B, R); if (R[0]>=w+1&&R[1]>=w+1) return -1; if (R[0] >= w+1) return 0; if (R[1] >= w+1) return 1; return -2; } int greaterValue(int NN, int WW) { N = NN, W = WW; const vector<int> cand = {1, 2, 3, 4, 5, 7, 8}; int lo = 0, hi = cand.size()-1; while (hi-lo >= 1) { int mid = (lo+hi)/2; int x = (2*mid<=W?cmp(cand[mid]):-2); if (x>=0) return x; if (x==-1) lo = mid+1; if (x==-2) hi = mid-1; } int x = cmp(cand[hi]); assert(x>=0); return x; } void allValues(int NN, int WW, int *P) { N = NN, W = WW; vector<int> left, right; rep(i, N) perm[i] = -1; vector<int> all; rep(i, N) all.pb(i); solve(1, N, all); rep(i, N) P[i] = perm[i]; }

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from koala.cpp:13:
koala.cpp: In function 'void solve(int, int, std::vector<int>)':
koala.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(r-l+1 == set.size());
          ~~~~~~^~~~~~~~~~~~~
koala.cpp: In function 'int solve2(int, int, std::vector<int>)':
koala.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(r-l+1 == set.size());
          ~~~~~~^~~~~~~~~~~~~
koala.cpp:102:11: warning: unused variable 'left' [-Wunused-variable]
       int left = (r-l+1)-right;
           ^~~~
#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...