题解

题目分析

这是一道基于交互式算法和博弈论的题目，需要与 Koala 系统进行交互来解决问题。

解题思路

1. 问题建模

• 与 Koala 系统交互，通过 playRound(B, R) 函数获取信息
• 需要实现四个关键函数：minValue、maxValue、greaterValue、allValues
• 使用位集 bitset<N> 优化空间使用

2. 最小值查找

• 使用简单策略：只给第一个元素分配权重
• 通过 playRound 比较不同元素
• 利用返回值判断元素大小关系

3. 最大值查找

• 使用预定义的阈值数组 maxVt[] = {0,1,2,4,11}
• 通过多次 playRound 操作缩小搜索范围
• 动态调整搜索策略，逐步淘汰较小元素

4. 比较函数

• 实现 greaterValue 函数比较两个元素
• 使用二分查找优化比较过程
• 处理边界情况和特殊情况

5. 全排序算法

• 实现 allValues 函数对所有元素排序
• 使用分治策略：solve 函数递归处理
• 特殊处理 $W = 2N$ 的情况，使用稳定排序

6. 关键技巧

• 使用 memset 初始化数组
• 利用 bitset 的高效位操作
• 通过多次交互获取足够信息
• 分治算法优化排序过程

时间复杂度

• 最小值：$O(1)$
• 最大值：$O(\log n)$
• 比较：$O(\log W)$
• 全排序：$O(n \log n)$

#include<bits/stdc++.h>
#include "koala.h"
#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define ll long long
#define INF 0x3f3f3f3f
#define INF64 1e18
using namespace std;

constexpr int N=105;

bitset<N> vis;

int B[N],R[N];

int minValue(int N, int W) {
	memset(B,0,sizeof B);
	B[0]=1;
	playRound(B,R);
	for(int i=0;i<N;i++){
		if(R[i]<=B[i]) return i;
	}
    return 0;
}


int maxVt[5]={0,1,2,4,11};

int maxValue(int N, int W) {
	vector<int> now;
	now.clear();
	for(int i=0;i<N;i++) now.push_back(i);
	vis.reset();

	for(int t=1;t<=4;t++){
		memset(B,0,sizeof B);
		for(auto x:now) B[x]=maxVt[t];
		playRound(B,R);
		for(int i=0;i<N;i++)
			if(R[i]<=B[i]) vis[i]=1;
		now.clear();
		for(int i=0;i<N;i++)
			if(vis[i]==0) now.push_back(i);
	}
	return now[0];
}


int greaterValue(int N, int W) {
	int l=1,r=min(9,W/2),mid;
	while(l<=r){
		mid=l+r>>1;
		memset(B,0,sizeof B);
		B[0]=mid,B[1]=mid;
		playRound(B,R);
		if(R[0]>B[0]&&R[1]<=B[1]) return 0;
		if(R[0]<=B[0]&&R[1]>B[1]) return 1;
		if(R[0]>B[0]) l=mid+1;
		else r=mid-1;
	}
	return 0;
}

int allW,ap[N];
bool cmp(int x,int y){
	memset(B,0,sizeof B);
	B[x]=allW/2;B[y]=allW/2;
	playRound(B,R);
	if(R[x]>B[x]) return 0;
	return 1;
}

int res[N];

int get_divide(int l,int r){
	for(int i=1;i<=r;i++){
		int t=r-l+1,pos=1,res=0;
		for(int j=r;j>=l;j--){
			t-=i+1;
			if(t<0){
				t=-t;
				if(pos+t-1>=l) break;
				if((pos+pos+t-1)*t/2>=j) break;
				pos+=t;
				t=0;
			}
			res++;
		}
		if(res!=0&&res!=r-l+1) return i;
	}
	return -1;
}

void solve(vector<int> now,int l,int r){
	if(l==r){
		res[now[0]]=l;
		return;
	}
	int t=get_divide(l,r);
	memset(B,0,sizeof B);
	for(auto x:now) B[x]=t;
	playRound(B,R);
	vector<int> x1,x2;
	for(auto x:now) 
		if(R[x]<=B[x]) x1.push_back(x);
		else x2.push_back(x);
	solve(x1,l,l+x1.size()-1);
	solve(x2,l+x1.size(),r);
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
		allW=W;
		for(int i=0;i<N;i++) ap[i]=i;
		stable_sort(ap,ap+N,cmp);
		for(int i=0;i<N;i++) P[ap[i]]=i+1;
		return;
    } else {
		vector<int> now;
		for(int i=0;i<N;i++) now.push_back(i);
		solve(now,1,N);
		for(int i=0;i<N;i++) P[i]=res[i];
    }
}