QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#67777#2293. Boredom BusterHe_RenWA 917ms11016kbC++232.3kb2022-12-12 01:15:172022-12-12 01:15:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-12 01:15:20]
  • 评测
  • 测评结果:WA
  • 用时:917ms
  • 内存:11016kb
  • [2022-12-12 01:15:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;

int n;

#ifdef He_Ren

//mt19937_64 gen((unsigned long long)new char ^ time(0));
mt19937_64 gen(0);

int p[MAXN];

void init(void)
{
	for(int i=1; i<=n; ++i)
		p[i] = (i+1) / 2;
	shuffle(p+1, p+n+1, gen);
}

array<int,2> ask(int x,int y)
{
	printf("ask %d %d\n",x,y);
	if(gen() % 2) swap(p[x], p[y]);
	array<int,2> res = {p[x], p[y]};
	if(gen() % 2) swap(p[x], p[y]);
	return res;
}

void answer(int ans[])
{
	printf("  p: ");
	for(int i=1; i<=n; ++i)
		printf("%d ",p[i]);
	printf("\n");
	
	printf("ans: ");
	for(int i=1; i<=n; ++i)
		printf("%d ",ans[i]);
	printf("\n");
}

#else

void init(void)
{
	
}

array<int,2> ask(int x,int y)
{
	printf("? %d %d\n",x,y);
	fflush(stdout);
	array<int,2> res;
	scanf("%d%d",&res[0],&res[1]);
	return res;
}

void answer(int ans[])
{
	printf("! ");
	for(int i=1; i<=n; ++i)
		printf("%d ",ans[i]);
	printf("\n");
	fflush(stdout);
}

#endif

array<int,2> a[MAXN * 2], b[MAXN * 2];
vector<int> pos[MAXN];

int main(void)
{
	scanf("%d",&n);
	
	init();
	
	for(int i=1; i<=n/2; ++i)
	{
		a[i] = {2*i-1, 2*i};
		b[i] = ask(a[i][0], a[i][1]);
		pos[b[i][0]].emplace_back(i);
		pos[b[i][1]].emplace_back(i);
	}
	
	auto change = [&] (int i,int x,int y)
	{
		if(pos[i][0] == x) pos[i][0] = y;
		if(pos[i][1] == x) pos[i][1] = y;
	};
	
	static int ans[MAXN];
	for(int i=1; i<=n/2; ++i)
	{
		int x = pos[i][0], y = pos[i][1];
		if(x == y)
		{
			ans[a[x][0]] = ans[a[x][1]] = i;
			continue;
		}
		if(b[x][1] == i) swap(b[x][0], b[x][1]);
		if(b[y][1] == i) swap(b[y][0], b[y][1]);
		
		while(1)
		{
			auto cur = ask(a[x][0], a[y][0]);
			if((cur[0] == i) == (cur[1] == i))
			{
				if(cur[0] != i)
				{
					swap(a[x][0], a[x][1]);
					swap(a[y][0], a[y][1]);
				}
				
				change(b[x][1], x, y);
				swap(a[x][1], a[y][0]);
				swap(b[x][1], b[y][0]);
				pos[i] = {x, x};
				break;
			}
			
			cur = ask(a[x][0], a[x][1]);
			if((cur[0] == i) == (cur[1] == i))
			{
				if(cur[0] != i)
				{
					swap(x, y);
				}
				
				change(b[x][1], x, y);
				swap(b[x][1], b[y][0]);
				pos[i] = {x, x};
				break;
			}
		}
		
		ans[a[x][0]] = ans[a[x][1]] = i;
	}
	
	answer(ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 917ms
memory: 11016kb

input:

100000
14243 13962
6948 22252
19244 19543
38903 11287
38236 8431
8855 44004
32239 28696
4163 13408
34466 26456
34636 16506
17476 19659
41596 45165
44174 8145
32853 13855
13860 32650
39829 40439
26857 16321
28351 11239
14823 35976
18843 47987
13886 18541
1370 15381
16164 41277
10418 10077
1431 40902
...

output:

? 1 2
? 3 4
? 5 6
? 7 8
? 9 10
? 11 12
? 13 14
? 15 16
? 17 18
? 19 20
? 21 22
? 23 24
? 25 26
? 27 28
? 29 30
? 31 32
? 33 34
? 35 36
? 37 38
? 39 40
? 41 42
? 43 44
? 45 46
? 47 48
? 49 50
? 51 52
? 53 54
? 55 56
? 57 58
? 59 60
? 61 62
? 63 64
? 65 66
? 67 68
? 69 70
? 71 72
? 73 74
? 75 76
? 77 ...

result:

wrong answer Wrong answer: Too many guesses: 150093 (which is 58093 over).