#include "koala.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> pbds;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
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.
int B[N];
for(int i = 0; i < N; i++)
{
B[i]=0;
}
B[0]=1;
int R[N];
playRound(B,R);
for(int i = 0; i < N; i++)
{
if(R[i]<=B[i])
{
return i;
}
}
return 0;
}
int findMax(vi &vec)
{
int n = vec.size();
//cerr<<n<<'\n';
static int B[100];
static int R[100];
static bool good[100];
if(n==1) return vec[0];
for(int i = 0; i < 100; i++)
{
good[i]=0;
B[i]=0;
}
for(int i=0;i<vec.size();i++)
{
good[vec[i]]=1;
B[vec[i]]=100/n;
}
playRound(B,R);
vec.clear();
for(int i=0;i<100;i++)
{
if(good[i]&&R[i]>B[i])
{
vec.pb(i);
}
}
return findMax(vec);
}
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.
vi v;
for(int i=0;i<N;i++) v.pb(i);
return findMax(v);
}
int testgreatervalue(int x)
{
static int B[100];
static int R[100];
for(int i = 0; i < 100; i++) B[i] = 0;
B[0]=B[1]=x;
playRound(B,R);
bool selecta = 0;
bool selectb = 0;
if(R[0]>B[0]) selecta=1;
if(R[1]>B[1]) selectb=1;
if(selecta^selectb)
{
if(selecta) return 0;
else return 1;
}
else
{
if(selecta) return -1;
else return -2;
}
}
int mm[6] = {1,2,4,6,7,8};
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.
int lo = 0; int hi = 5;
while(lo<=hi)
{
int mid = (lo+hi)>>1;
int tmp = testgreatervalue(mm[mid]);
if(tmp>=0)
{
//ofstream fout("koalapre.txt");
//cout<<mm[mid]<<",";
return tmp;
}
if(tmp==-1)
{
lo=mid+1;
}
else
{
hi=mid-1;
}
}
//cout<<"ERROR\n";
return 0;
}
ii dp[101][101];
int moves[101][101];
typedef long double ld;
const int NN = 100;
int test(int x, int p1, int p2)
{
static int B[100];
static int R[100];
for(int i = 0; i < 100; i++) B[i] = 0;
B[p1]=B[p2]=x;
playRound(B,R);
bool selecta = 0;
bool selectb = 0;
if(R[p1]>B[p1]) selecta=1;
if(R[p2]>B[p2]) selectb=1;
if(selecta^selectb)
{
if(selecta) return 0;
else return 1;
}
else
{
if(selecta) return -1;
else return -2;
}
}
int greedydp(int l, int r, int a, int b) //a from [1, l - 1], b from [l, r]
{
vector<pair<ld,int> > vec;
for(int i = 1; i < l; i++)
{
vec.pb(mp(ld(i)/ld(a),i));
}
for(int i = l; i <= r; i++)
{
vec.pb(mp(ld(i)/ld(b),i));
}
sort(vec.rbegin(),vec.rend());
int sum=0;
int cnt = r;
for(int i=0;i<r;i++)
{
if(vec[i].se>=l)
{
if(sum+b<=r)
{
cnt--;
sum+=b;
}
else
{
continue;
}
}
else
{
if(sum+a<=r)
{
sum+=a;
}
else continue;
}
}
return cnt;
}
int realdp(int l, int r, int a, int b)
{
//cerr<<l<<' '<<r<<' '<<a<<' '<<b<<'\n';
pair<int,int> dp2[r+1][r+1];
for(int i = 0; i <= r; i++)
{
for(int j= 0;j<=r;j++)
{
dp2[i][j]=mp(-1,-1);
}
}
dp2[1][0] = mp(0,0);
if(a<=r)
{
if(l==0) dp2[1][a] = mp(1,1);
else dp2[1][a] = mp(1,0);
}
for(int i = 2; i <= r; i++)
{
for(int j = 0; j <= r; j++)
{
dp2[i][j] = dp2[i-1][j];
int cost = a;
if(i>=l) cost=b;
if(j>=cost)
{
int cc=0;
if(i>=l) cc++;
dp2[i][j] = max(dp2[i][j],mp(dp2[i-1][j-cost].fi+i,dp2[i-1][j-cost].se+cc));
}
}
}
ii best=mp(-1,-1);
for(int i = 0; i <= r; i++)
{
best=max(best,dp2[r][i]);
}
//cerr<<l<<' '<<r<<' '<<a<<' '<<b<<'\n';
return r-best.se;
}
const int C1 = 20;
const int C2 = 30;
int solve(int l, int r)
{
//
if(moves[l][r]!=-1) return moves[l][r];
if(l>r) return 0;
if(l==r)
{
return (moves[l][r]=0);
}
if(r-l>=2)
{
//cerr<<"SOLVE : "<<l<<' '<<r<<'\n';
int cc=0;
ii best = mp(-1,-1);
int bestres = 100000;
for(int a = 1; a < C1; a++)
{
for(int b = a + 1; b < C2; b++)
{
if((a-1)*l+(b-1)*(r-l)>NN) continue;
int mid = 0;
if(r-l>8) mid = greedydp(l,r,a,b);
else mid = realdp(l,r,a,b);
//if(l==1&&r==10) cerr<<l<<' '<<r<<' '<<a<<' '<<b<<' '<<mid<<'\n';
if(mid+1==l||r==mid) continue;
int mov = 1 + solve(l,mid) + solve(mid+1,r);
if(mov<bestres)
{
bestres=mov;
best=mp(a,b);
cc++;
}
if(cc>=3) break;
}
if(cc>=3) break;
}
if(bestres==100000) assert(0);
dp[l][r] = best;
return (moves[l][r] = bestres);
}
else
{
return (moves[l][r]=1);
}
}
int ans[101];
bool mode2;
const int MAGIC1[100] = {1,1,1,2,2,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8};
const int MAGIC2[100] = {1,1,1,2,2,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8};
void play(int l, int r, vi vec, vi L)
{
//cerr<<l<<' '<<r<<'\n';
if(l==r)
{
ans[vec[0]] = l;
return ;
}
if(r-l<2)
{
int mid = MAGIC1[l-1];
int tmp = test(mid,vec[0],vec[1]);
if(tmp>=0)
{
if(tmp==0)
{
ans[vec[0]] = l+1;
ans[vec[1]] = l;
}
else
{
ans[vec[0]]=l;
ans[vec[1]]=l+1;
}
return ;
}
assert(tmp>=0);
/*
int lo = 0; int hi = 5;
while(lo<=hi)
{
int mid = (lo+hi)>>1;
int tmp = test(mm[mid],vec[0],vec[1]);
if(tmp>=0)
{
//ofstream fout("koalapre.txt");
//cout<<mid<<",";
if(tmp==0)
{
ans[vec[0]] = l+1;
ans[vec[1]] = l;
}
else
{
ans[vec[0]]=l;
ans[vec[1]]=l+1;
}
return ;
}
if(tmp==-1)
{
lo=mid+1;
}
else
{
hi=mid-1;
}
}
*/
}
if(l>r) return ;
if(moves[l][r]==-1) solve(l,r);
ii mov = dp[l][r];
//cerr<<"HERE\n";
static int B[100];
static int R[100];
assert(L.size()==l-1);
assert(vec.size()==r-l+1);
//cerr<<l<<' '<<r<<' '<<mov.fi<<' '<<mov.se<<'\n';
for(int i = 0; i < NN; i++)
{
B[i]=0;
}
for(int i = 0; i < L.size(); i++)
{
B[L[i]]=mov.fi-1;
}
for(int i = 0; i < vec.size(); i++)
{
B[vec[i]]=mov.se-1;
}
playRound(B,R);
vi le,ri;
vi Ltmp = L;
int mid = r+1;
//cerr<<"HERE\n";
for(int i = 0; i < vec.size(); i++)
{
if(R[vec[i]]>B[vec[i]])
{
ri.pb(vec[i]);
mid--;
}
else
{
le.pb(vec[i]);
}
}
//cerr<<l<<' '<<mid<<' '<<r<<' '<<mov.fi<<' '<<mov.se<<'\n';
for(int i=0;i<le.size();i++) Ltmp.pb(le[i]);
play(l,mid-1,le,L);
play(mid,r,ri,Ltmp);
}
bool cmp(int x, int y)
{
static int B[100];
static int R[100];
for(int i=0;i<100;i++) B[i]=0;
B[x]=100; B[y]=100;
playRound(B,R);
if(R[x]>B[x]) return false;
return true;
}
void allValues(int N, int W, int *P) {
memset(moves,-1,sizeof(moves));
if (W == 2*N)
{
for(int i=0;i<N;i++) P[i]=i+1;
sort(P,P+N,cmp);
// 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.
// You may leave this block unmodified if you are not attempting this
// subtask.
vi v,w;
mode2=0;
for(int i=0;i<N;i++) v.pb(i);
play(1,N,v,w);
for(int i=0;i<N;i++)
{
P[i]=ans[i];
}
}
}
Compilation message
koala.cpp: In function 'int findMax(vi&)':
koala.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vec.size();i++)
~^~~~~~~~~~~
In file included from /usr/include/c++/7/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45:0,
from /usr/include/c++/7/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/7/ext/pb_ds/assoc_container.hpp:48,
from koala.cpp:3:
koala.cpp: In function 'void play(int, int, vi, vi)':
koala.cpp:359:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(L.size()==l-1);
~~~~~~~~^~~~~
koala.cpp:360:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(vec.size()==r-l+1);
~~~~~~~~~~^~~~~~~
koala.cpp:366:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < L.size(); i++)
~~^~~~~~~~~~
koala.cpp:370:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec.size(); i++)
~~^~~~~~~~~~~~
koala.cpp:379:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec.size(); i++)
~~^~~~~~~~~~~~
koala.cpp:392:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<le.size();i++) Ltmp.pb(le[i]);
~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
384 KB |
Output is correct |
| 2 |
Correct |
10 ms |
384 KB |
Output is correct |
| 3 |
Correct |
10 ms |
384 KB |
Output is correct |
| 4 |
Correct |
9 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
384 KB |
Output is correct |
| 2 |
Correct |
22 ms |
384 KB |
Output is correct |
| 3 |
Correct |
22 ms |
384 KB |
Output is correct |
| 4 |
Correct |
22 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
384 KB |
Output is correct |
| 2 |
Correct |
97 ms |
384 KB |
Output is correct |
| 3 |
Correct |
86 ms |
384 KB |
Output is correct |
| 4 |
Correct |
85 ms |
384 KB |
Output is correct |
| 5 |
Correct |
83 ms |
384 KB |
Output is correct |
| 6 |
Correct |
84 ms |
384 KB |
Output is correct |
| 7 |
Correct |
83 ms |
384 KB |
Output is correct |
| 8 |
Correct |
86 ms |
384 KB |
Output is correct |
| 9 |
Correct |
90 ms |
384 KB |
Output is correct |
| 10 |
Correct |
86 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
315 ms |
564 KB |
Output is correct |
| 2 |
Correct |
298 ms |
632 KB |
Output is correct |
| 3 |
Correct |
301 ms |
632 KB |
Output is correct |
| 4 |
Correct |
308 ms |
632 KB |
Output is correct |
| 5 |
Correct |
296 ms |
572 KB |
Output is correct |
| 6 |
Correct |
293 ms |
504 KB |
Output is correct |
| 7 |
Correct |
310 ms |
600 KB |
Output is correct |
| 8 |
Correct |
300 ms |
504 KB |
Output is correct |
| 9 |
Correct |
318 ms |
504 KB |
Output is correct |
| 10 |
Correct |
318 ms |
632 KB |
Output is correct |
| 11 |
Correct |
309 ms |
504 KB |
Output is correct |
| 12 |
Correct |
288 ms |
504 KB |
Output is correct |
| 13 |
Correct |
296 ms |
504 KB |
Output is correct |
| 14 |
Correct |
312 ms |
504 KB |
Output is correct |
| 15 |
Correct |
303 ms |
520 KB |
Output is correct |
| 16 |
Correct |
291 ms |
504 KB |
Output is correct |
| 17 |
Correct |
321 ms |
504 KB |
Output is correct |
| 18 |
Correct |
314 ms |
504 KB |
Output is correct |
| 19 |
Correct |
306 ms |
504 KB |
Output is correct |
| 20 |
Correct |
295 ms |
504 KB |
Output is correct |
| 21 |
Correct |
290 ms |
504 KB |
Output is correct |
| 22 |
Correct |
318 ms |
632 KB |
Output is correct |
| 23 |
Correct |
294 ms |
504 KB |
Output is correct |
| 24 |
Correct |
319 ms |
504 KB |
Output is correct |
| 25 |
Correct |
315 ms |
504 KB |
Output is correct |
| 26 |
Correct |
313 ms |
504 KB |
Output is correct |
| 27 |
Correct |
319 ms |
760 KB |
Output is correct |
| 28 |
Correct |
297 ms |
504 KB |
Output is correct |
| 29 |
Correct |
303 ms |
572 KB |
Output is correct |
| 30 |
Correct |
313 ms |
504 KB |
Output is correct |
| 31 |
Correct |
318 ms |
504 KB |
Output is correct |
| 32 |
Correct |
313 ms |
596 KB |
Output is correct |
| 33 |
Correct |
300 ms |
504 KB |
Output is correct |
| 34 |
Correct |
302 ms |
636 KB |
Output is correct |
| 35 |
Correct |
310 ms |
504 KB |
Output is correct |
| 36 |
Correct |
314 ms |
504 KB |
Output is correct |
| 37 |
Correct |
309 ms |
504 KB |
Output is correct |
| 38 |
Correct |
296 ms |
484 KB |
Output is correct |
| 39 |
Correct |
306 ms |
760 KB |
Output is correct |
| 40 |
Correct |
315 ms |
504 KB |
Output is correct |
