http://codeforces.com/problemset/gymProblem/100685/J
这个交互题实在太过JB。。。。感觉不写一下对不起自己。。。
题意：给你n(n<=1000)个元素a1-an，他们之间存在cmp，但是cmp函数是不可递推的。现在你有不超过1W次的机会询问ai与aj的cmp函数，要求出一个长度为n的序列，满足cmp(ax[i],ax[i+1])=true。恩大概就这个意思。
一开始方向想错了，想什么图论拓扑找最长链这种东西_(:зゝ∠)_居然没有注意10000大概就是nlog的复杂度。nlog，有序，这TM不就是快拍吗_(:зゝ∠)_然后问题来了，手打快排效率不稳定，很难到达刚好nlog，c++STL的sort也不稳定，归并大概可以吧（没试过），但实际上有一个STL叫stable_sort可以刚好nlog次，上这个就行了
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int a[1005];
int n;
char c[10];
bool cmp(int k1,int k2){
printf("1 %d %d\n",k1,k2);
cout.flush();
scanf("%s",&c);
if(c[0]=='Y')return true;
if(c[0]=='N')return false;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)a[i]=i;
stable_sort(a+1,a+1+n,cmp);
printf("0");
for(int i=1;i<=n;i++)printf(" %d",a[i]);
}
2016年1月16日 12:20
我不做人啦
2016年1月16日 12:21
我不做人啦