Submission #739523

#TimeUsernameProblemLanguageResultExecution timeMemory
739523myrcellaKoala Game (APIO17_koala)C++17
100 / 100
53 ms396 KiB
//by szh #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl #define pq priority_queue #define inf 0x3f #define rep(i,a,b) for (int i=a;i<(b);i++) #define MP make_pair #define SZ(x) (int(x.size())) #define ll long long #define mod 1000000007 #define ALL(x) x.begin(),x.end() void inc(int &a,int b) {a=(a+b)%mod;} void dec(int &a,int b) {a=(a-b+mod)%mod;} int lowbit(int x) {return x&(-x);} ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;} #include "koala.h" int minValue(int N, int W) { int b[111]; b[0] = 1; rep(i,1,N) b[i] = 0; int a[111]; playRound(b,a); rep(i,0,N) if (a[i]<=b[i]) return i; assert(1==2); // TODO: Implement Subtask 1 solution here. // You may leave this function unmodified if you are not attempting this // subtask. } int maxValue(int N, int W) { int n=N; int a[111],b[111]; rep(i,0,n) a[i] = 1; playRound(a,b); int a2[111],b2[111]; rep(i,0,n) { if (b[i]<=a[i]) a2[i] = 0; else a2[i] = 2; } playRound(a2,b2); int a3[111],b3[111]; rep(i,0,n) { if (a2[i]==0 or b2[i]<=a2[i]) a3[i] = 0; else a3[i] = 4; } playRound(a3,b3); int a4[111],b4[111]; rep(i,0,n) { if (a3[i]==0 or b3[i]<=a3[i]) a4[i] = 0; else a4[i] = 11; } playRound(a4,b4); rep(i,0,n) if (a4[i]!=0 and b4[i]>a4[i]) return i; assert(1==2); // TODO: Implement Subtask 2 solution here. // You may leave this function unmodified if you are not attempting this // subtask. return 0; } int mx = 0,mn=100; set <int> s; int greaterValue(int N, int W) { int l = 1,r = 14; while (l<=r) { // cout<<l<<" "<<r<<endl; int mid = l+r>>1; int a[111],b[111]; a[0] = a[1] = mid; rep(i,2,N) a[i] = 0; playRound(a,b); if (a[0]<b[0] and a[1]<b[1]) l = mid+1; else if (a[0]>=b[0] and a[1]>=b[1]) r = mid-1; else { if (a[0]<b[0]) return 0; else return 1; } } assert(1==2); // TODO: Implement Subtask 3 solution here. // You may leave this function unmodified if you are not attempting this // subtask. return 0; } int mygreaterValue(int x,int y) { int l = 1,r = 14; while (l<=r) { // cout<<l<<" "<<r<<endl; int mid = l+r>>1; int a[111],b[111]; a[x] = a[y] = mid; rep(i,0,100) if (i!=x and i!=y) a[i] = 0; playRound(a,b); if (a[x]<b[x] and a[y]<b[y]) l = mid+1; else if (a[x]>=b[x] and a[y]>=b[y]) r = mid-1; else { if (a[x]<b[x]) return 0; else return 1; } } assert(1==2); // TODO: Implement Subtask 3 solution here. // You may leave this function unmodified if you are not attempting this // subtask. return 0; } int ohno[111][111]; bool cmp(int x,int y) { if (ohno[x][y]!=-1) { assert(ohno[x][y]+ohno[y][x]==1); return ohno[x][y]; } int a[111],b[111]; rep(i,0,100) { if (i==x or i==y) a[i] = 100; else a[i] = 0; } playRound(a,b); rep(i,0,100) { if (i==x or i==y) continue; if (b[y]>100 and ohno[i][x]==1) ohno[i][y]=1,ohno[y][i]=0; //x<y if (b[y]>100 and ohno[y][i]==1) ohno[x][i]=1,ohno[i][x]=0; if (a[y]>100 and ohno[i][y]==1) ohno[i][x]=1,ohno[x][i]=0;//x>y if (a[y]>100 and ohno[x][i]==1) ohno[y][i]=1,ohno[i][y]=0; } ohno[x][y] = (b[y]>100); ohno[y][x] = (b[x]>100); return b[y]>100; } void msort(int l,int r,int *a) { if (l>=r) return; int mid=l+r>>1; msort(l,mid,a);msort(mid+1,r,a); vector <int> tmp; int cur1=l,cur2=mid+1; while (cur1<=mid and cur2<=r) if (cmp(a[cur1],a[cur2])) tmp.pb(a[cur1++]);else tmp.pb(a[cur2++]); while (cur1<=mid) tmp.pb(a[cur1++]); while (cur2<=r) tmp.pb(a[cur2++]); rep(i,0,SZ(tmp)) a[l+i] = tmp[i]; return; } void mmsort(int l,int r,int *a) { if (l>=r) return; int mid=l+r>>1; mmsort(l,mid,a);mmsort(mid+1,r,a); vector <int> tmp; int cur1=l,cur2=mid+1; while (cur1<=mid and cur2<=r) if (mygreaterValue(a[cur1],a[cur2])) tmp.pb(a[cur1++]);else tmp.pb(a[cur2++]); while (cur1<=mid) tmp.pb(a[cur1++]); while (cur2<=r) tmp.pb(a[cur2++]); rep(i,0,SZ(tmp)) a[l+i] = tmp[i]; return; } int ans[111]; void solve (vector <int> pos,int l,int r) { if (l==r) ans[pos[0]] = l; else { int cur = min(100/(r-l+1),(int)sqrt(2*l)); int tmp[111],res[111]; rep(i,0,100) tmp[i] = 0; for (auto it:pos) tmp[it] = cur; playRound(tmp,res); vector <int> low,high; for (auto i:pos) if (res[i]>tmp[i]) high.pb(i);else low.pb(i); assert(!high.empty() and !low.empty()); solve(low,l,l+SZ(low)-1); solve(high,l+SZ(low),r); } } void allValues(int N, int W, int *P) { int n = N; if (W == 2*N) { // TODO: Implement Subtask 4 solution here. // You may leave this block unmodified if you are not attempting this // subtask. memset(ohno,-1,sizeof(ohno)); int a[111]; rep(i,0,n) a[i] = i; msort(0,n-1,a); rep(i,0,n) P[a[i]] = i+1; } else { vector <int> tmp; rep(i,0,n) tmp.pb(i); solve(tmp,1,n); rep(i,0,n) P[i] = ans[i]; // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. } }

Compilation message (stderr)

koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:78:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   int mid = l+r>>1;
      |             ~^~
koala.cpp: In function 'int mygreaterValue(int, int)':
koala.cpp:101:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |   int mid = l+r>>1;
      |             ~^~
koala.cpp: In function 'void msort(int, int, int*)':
koala.cpp:147:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |  int mid=l+r>>1;
      |          ~^~
koala.cpp: In function 'void mmsort(int, int, int*)':
koala.cpp:160:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |  int mid=l+r>>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...