QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353602#6303. Inversioncrsfaa#WA 71ms6712kbC++142.4kb2024-03-14 12:02:302024-03-14 12:02:30

Judging History

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

  • [2024-03-14 12:02:30]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:6712kb
  • [2024-03-14 12:02:30]
  • 提交

answer

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int p[2005];
int p0[2005];
int cnt;
map<pair<int,int>,int> mp;
bool ask(int l,int r)
{
	if(l>=r) return 0;
	if(mp.count({l,r})) return mp[{l,r}];
	printf("? %d %d\n",l,r);
	cnt++;
	fflush(stdout);
//	int c=0;
//	for(int i=l;i<=r;i++)
//		for(int j=i+1;j<=r;j++)
//			c^=p0[i]>p0[j];
//	cout<<"q "<<c<<endl;
	int c;
	cin>>c;
	return mp[{l,r}]=c;
}
bool get(int l,int r)
{
	bool fl=0;
	if(l>r) swap(l,r),fl=1;
	return ask(l,r)^ask(l+1,r)^ask(l,r-1)^ask(l+1,r-1)^fl;
}
bool cmp(int x,int y)
{
	return p[x]<p[y];
}
int qwq[2005];
void solve(int l,int r)
{
	if(l>=r)
	{
		p[l]=1;
		return;
	}
	int mid=l+r>>1,i,j,cnt=0;
	solve(l,mid),solve(mid+1,r);
	deque<int> a,b;
	for(i=l;i<=mid;i++)
		a.push_back(i);
	for(;i<=r;i++)
		b.push_back(i);
	sort(a.begin(),a.end(),cmp);
	sort(b.begin(),b.end(),cmp);
	if(rand()%2)
	{
		qwq[mid-1]=0;
		for(i=mid;i<=r;i++)
			qwq[i]=ask(l,i);
		for(i=r;i>mid;i--)
			qwq[i]^=qwq[i-1];
		for(i=mid+1;i<=r;i++)
		{
//			cout<<l<<' '<<r<<' '<<i<<':'<<qwq[i]<<endl;
			for(j=mid+1;j<i;j++)
				qwq[i]^=(p[j]>p[i]);
			qwq[i]^=(mid-l+1)%2;
			
		}	
		int cnt2=0;
		while(a.size()&&b.size())
			if(cnt2==qwq[b.front()]&&get(a.front(),b.front()))
				p[b.front()]=++cnt,b.pop_front();
			else
				p[a.front()]=++cnt,a.pop_front(),cnt2^=1;
	}
	else
	{
		qwq[mid+2]=0;
		for(i=mid+1;i>=l;i--)
			qwq[i]=ask(i,r);
		for(i=l;i<=mid;i++)
			qwq[i]^=qwq[i+1];
		for(i=mid;i>=l;i--)
		{
			for(j=i+1;j<=mid;j++)
				qwq[i]^=(p[i]>p[j]);
		}
		int cnt2=0;	
		while(a.size()&&b.size())
			if(cnt2==qwq[a.front()]&&!get(a.front(),b.front()))
				p[a.front()]=++cnt,a.pop_front();
			else
				p[b.front()]=++cnt,b.pop_front(),cnt2^=1;
	}
	for(auto x:a)
		p[x]=++cnt;
	for(auto x:b)
		p[x]=++cnt;
//	cout<<l<<' '<<r<<':';
//	for(int i=l;i<=r;i++)
//		cout<<p[i]<<' ';
//	puts("");
}
/*
10
1 10 9 3 4 6 7 8 2 5
*/
int main()
{
	srand(114514);
	int n=read(),i;
	for(i=1;i<=n;i++)
		p0[i]=i;
	random_shuffle(p0+1,p0+1+n);
//	for(i=1;i<=n;i++)
//		cout<<p0[i]<<' ';
//	puts("");
	solve(1,n);
	printf("! ");
	for(i=1;i<=n;i++)
		printf("%d ",p[i]);
	puts("");
	fflush(stdout);
//	cout<<cnt;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 71ms
memory: 6712kb

input:

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

output:

? 1 2
? 3 4
? 2 4
? 1 4
? 1 3
? 2 3
? 5 6
? 7 8
? 6 8
? 5 8
? 5 7
? 6 7
? 4 8
? 3 8
? 2 8
? 1 8
? 1 5
? 2 5
? 1 7
? 2 7
? 3 7
? 9 10
? 11 12
? 10 12
? 9 12
? 10 11
? 9 11
? 13 14
? 15 16
? 14 16
? 13 16
? 14 15
? 13 15
? 9 13
? 9 14
? 9 15
? 9 16
? 11 14
? 12 14
? 11 13
? 12 13
? 10 15
? 10 14
? 10 ...

result:

wrong output format Unexpected end of file - int32 expected