QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673807#6303. Inversionsc2005#WA 82ms19356kbC++201.4kb2024-10-25 10:28:002024-10-25 10:28:01

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 10:28:01]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:19356kb
  • [2024-10-25 10:28:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
typedef long long ll;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    a=f*x;
}
inline void write(ll x){
    char P[105];int w=0;
    if(x<0)putchar('-'),x=-x;
    if(x==0)printf("0");
    while(x)P[++w]=x%10+'0',x/=10;
    for(int i=w;i;i--)putchar(P[i]);
}
const int N=2e3+10;

int a[N];
int qa[N][N];
int query(int l,int r){
	if(r<l)swap(l,r);
	if(l==r)return 0;
	if(qa[l][r]!=-1)return qa[l][r];
	cout<<"? "<<l<<" "<<r<<endl;
	int x;cin>>x;
	return qa[l][r]=x;
}
bool cmp(int x,int y){
	int tt=0;
	if(x>y){swap(x,y);tt=1;}
	if(x==y)return 0;
	if(y-x==1){
		return (query(x,y))^tt;
	}
	int x1=query(x,y),x2=query(x+1,y),x3=query(x,y-1),x4=query(x+1,y-1);
	int t=x1+x4-x2-x3;
	t=(t+4)%2;
	//printf("%d %d %d %d\n",x,y,t,tt);
	return (t)^tt;
}
int ans[N];
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			qa[i][j]=-1;
	for(int i=1;i<=n;++i)a[i]=i;
	sort(a+1,a+n+1,cmp);
	cout<<"! ";
	for(int i=1;i<=n;++i)ans[a[i]]=n+1-i;
	for(int i=1;i<=n;++i)cout<<ans[i]<<" ";
	cout<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

3
0
1
0

output:

? 1 2
? 2 3
? 1 3
! 2 3 1 

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 82ms
memory: 19356kb

input:

1993
1
0
1
1
0
0
1
1
1
1
1
1
0
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
0
0
1
1
1
0
0
0
1
0
1
1
0
0
0
1
1
0
1
1
1
0
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
0
1
1
0
1
0
0
0
0
1
0
1
1
1
0
1
1
1
0
1
0
1
1
0
0
0
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
0
1
0
0
0
1
1
0
1
0
0
0...

output:

? 2 997
? 3 997
? 2 996
? 3 996
? 997 1993
? 998 1993
? 997 1992
? 998 1992
? 2 1993
? 3 1993
? 2 1992
? 3 1992
? 1 2
? 2 3
? 2 4
? 3 4
? 2 5
? 3 5
? 2 1991
? 3 1991
? 2 1990
? 3 1990
? 2 1989
? 3 1989
? 2 1988
? 3 1988
? 2 1987
? 3 1987
? 2 6
? 3 6
? 2 1986
? 3 1986
? 2 7
? 3 7
? 2 1985
? 3 1985
? ...

result:

wrong output format Unexpected end of file - int32 expected