Submission #739523

#	Time	Username	Problem	Language	Result	Execution time	Memory
739523		myrcella	Koala Game (APIO17_koala)	C++17	100 / 100	53 ms	396 KiB

koala

//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;
      |          ~^~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 53 / 53