QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562002#7535. Limited Shuffle Restoringucup-team052#TL 1ms3840kbC++233.0kb2024-09-13 14:08:112024-09-13 14:08:12

Judging History

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

  • [2024-09-13 14:08:12]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3840kb
  • [2024-09-13 14:08:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

int ord[54][5], used[5], now[5], len;

void dfs(int u) {
	if (u == -1) {
		memcpy(ord[len], now, sizeof(ord[len]));
		++len;
		return;
	}
	int l = max(0, u - 2), r = 4;
	for (int i = l; i <= r; i++) {
		if (!used[i]) {
			used[i] = 1;
			now[i] = u;
			dfs(u - 1);
			used[i] = 0;
		}
	}
}

map <ull, pair <int, int> > f;
int n;

pair <ull, ull> gao(ull x, int u, int v) {
	ull v1 = 0, v2 = 0;
	for (int i = 0; i < 54; i++) {
		if ((x >> i) & 1) {
			if (ord[i][u] < ord[i][v]) v1 |= (1ull << i);
			else v2 |= (1ull << i);
		}
	}
	return make_pair(v1, v2);
}

int solve(ull x, int dep) {
	if ((x & -x) == x) return dep >= -1;
	for (int u = (x == (1ull << 54) - 1 ? 3 : 0); u < 4; u++) {
		for (int v = u + 1; v <= 4; v++) {
			pair <ull, ull> t = gao(x, u, v);
			int cc = max(__builtin_popcountll(t.first), __builtin_popcountll(t.second));
			if (__lg(cc) > dep) continue;
			int v1 = solve(t.first, dep - 1);
			if (!v1) continue;
			int v2 = solve(t.second, dep - 1);
			if (!v2) continue;
			f[x] = make_pair(u, v);
			return 1;
		}
	}
	return 0;
}

int ans[30005];
int last;

int query(int u, int v) {
	cout << "? " << u << " " << v << endl;
	char c;
	cin >> c;
	return c == '>';
}

int main() {
	dfs(4);
	solve((1ull << 54) - 1, 5);
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	if (n == 1) {
		cout << "! 1" << endl;
		return 0;
	}
	last = query(n - 1, n);
	int pos[5] = {0, 0, 0, n - 1, n};
	int i;
	for (i = n; i >= 5; i -= 3) {
		pos[0] = i - 4; pos[1] = i - 3; pos[2] = i - 2;
		ull now = (1ull << 54) - 1;
		int flag = 0;
		while ((now & -now) != now) {
			pair <int, int> t = f[now];
			int res;
			if (!flag) {
				flag = 1;
				res = last;
			} else {
				res = query(pos[t.first], pos[t.second]);
			}
			pair <ull, ull> v = gao(now, t.first, t.second);
			if (res) now = v.second;
			else now = v.first;
		}
		int id = 0;
		while ((1ull << id) != now) ++id;
		// fprintf(stderr, "id = %d\n", id);
		// for (int j = 0; j < 5; j++) fprintf(stderr, "ord[%d] = %d, pos[%d] = %d\n", j, ord[id][j], j, pos[j]);
		int pos0 = -1, pos1 = -1;
		for (int j = 0; j < 5; j++) {
			if (ord[id][j] >= 2) {
				ans[pos[j]] = i - 4 + ord[id][j];
			} else {
				if (ord[id][j] == 0) pos0 = pos[j];
				else pos1 = pos[j];
			}
		}
		assert(pos0 != -1 && pos1 != -1);
		if (pos0 < pos1) {
			last = 0;
		} else {
			last = 1;
			swap(pos0, pos1);
		}
		pos[3] = pos0; pos[4] = pos1;
	}
	// fprintf(stderr, "i = %d\n", i);
	for (; i >= 3; i--) {
		pos[2] = i - 2;
		int mx = last ? pos[3] : pos[4];
		if (query(pos[2], mx)) {
			mx = pos[2];
		} else {
			if (mx == pos[3]) {
				pos[3] = pos[2];
			} else {
				pos[4] = pos[3];
				pos[3] = pos[2];
			}
			last = query(pos[3], pos[4]);
		}
		ans[mx] = i;
	}
	if (last) ans[pos[3]] = 2, ans[pos[4]] = 1;
	else ans[pos[3]] = 1, ans[pos[4]] = 2;
	cout << "!";
	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: 3568kb

input:

5
>
<
<
>
<
<

output:

? 4 5
? 1 5
? 3 5
? 1 3
? 1 2
? 2 5
! 2 3 1 5 4

result:

ok yeah, seems ok, spent 6 queries of 13

Test #2:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

1

output:

! 1

result:

ok yeah, seems ok, spent 0 queries of 6

Test #3:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

2
>

output:

? 1 2
! 2 1

result:

ok yeah, seems ok, spent 1 queries of 8

Test #4:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

3
>
<
>

output:

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

result:

ok yeah, seems ok, spent 3 queries of 10

Test #5:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

4
>
<
>
<
>

output:

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

result:

ok yeah, seems ok, spent 5 queries of 11

Test #6:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

5
>
<
>
>
>
>

output:

? 4 5
? 1 5
? 3 5
? 2 5
? 3 4
? 2 4
! 1 4 5 3 2

result:

ok yeah, seems ok, spent 6 queries of 13

Test #7:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

6
>
<
>
>
>
>
<
>

output:

? 5 6
? 2 6
? 4 6
? 3 6
? 4 5
? 3 5
? 1 6
? 1 2
! 2 1 5 6 4 3

result:

ok yeah, seems ok, spent 8 queries of 15

Test #8:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

7
>
<
>
>
>
>
<
>
<
>

output:

? 6 7
? 3 7
? 5 7
? 4 7
? 5 6
? 4 6
? 2 7
? 2 3
? 1 2
? 1 3
! 2 3 1 6 7 5 4

result:

ok yeah, seems ok, spent 10 queries of 16

Test #9:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

8
>
<
>
>
>
>
<
>
>
>
>

output:

? 7 8
? 4 8
? 6 8
? 5 8
? 6 7
? 5 7
? 1 4
? 3 4
? 2 4
? 3 8
? 2 8
! 1 4 5 2 7 8 6 3

result:

ok yeah, seems ok, spent 11 queries of 18

Test #10:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

9
>
<
>
>
>
>
<
>
>
>
>
<
>

output:

? 8 9
? 5 9
? 7 9
? 6 9
? 7 8
? 6 8
? 2 5
? 4 5
? 3 5
? 4 9
? 3 9
? 1 5
? 1 2
! 2 1 5 6 3 8 9 7 4

result:

ok yeah, seems ok, spent 13 queries of 20

Test #11:

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

input:

10
>
<
>
>
>
>
<
>
>
>
>
<
>
<
>

output:

? 9 10
? 6 10
? 8 10
? 7 10
? 8 9
? 7 9
? 3 6
? 5 6
? 4 6
? 5 10
? 4 10
? 2 6
? 2 3
? 1 2
? 1 3
! 2 3 1 6 7 4 9 10 8 5

result:

ok yeah, seems ok, spent 15 queries of 21

Test #12:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

11
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>

output:

? 10 11
? 7 11
? 9 11
? 8 11
? 9 10
? 8 10
? 4 7
? 6 7
? 5 7
? 6 11
? 5 11
? 1 4
? 3 4
? 2 4
? 3 7
? 2 7
! 1 4 5 2 7 8 3 10 11 9 6

result:

ok yeah, seems ok, spent 16 queries of 23

Test #13:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

12
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>

output:

? 11 12
? 8 12
? 10 12
? 9 12
? 10 11
? 9 11
? 5 8
? 7 8
? 6 8
? 7 12
? 6 12
? 2 5
? 4 5
? 3 5
? 4 8
? 3 8
? 1 5
? 1 2
! 2 1 5 6 3 8 9 4 11 12 10 7

result:

ok yeah, seems ok, spent 18 queries of 25

Test #14:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

13
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
<
>

output:

? 12 13
? 9 13
? 11 13
? 10 13
? 11 12
? 10 12
? 6 9
? 8 9
? 7 9
? 8 13
? 7 13
? 3 6
? 5 6
? 4 6
? 5 9
? 4 9
? 2 6
? 2 3
? 1 2
? 1 3
! 2 3 1 6 7 4 9 10 5 12 13 11 8

result:

ok yeah, seems ok, spent 20 queries of 26

Test #15:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

14
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>

output:

? 13 14
? 10 14
? 12 14
? 11 14
? 12 13
? 11 13
? 7 10
? 9 10
? 8 10
? 9 14
? 8 14
? 4 7
? 6 7
? 5 7
? 6 10
? 5 10
? 1 4
? 3 4
? 2 4
? 3 7
? 2 7
! 1 4 5 2 7 8 3 10 11 6 13 14 12 9

result:

ok yeah, seems ok, spent 21 queries of 28

Test #16:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

15
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>

output:

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

result:

ok yeah, seems ok, spent 23 queries of 30

Test #17:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

16
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
<
>

output:

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

result:

ok yeah, seems ok, spent 25 queries of 31

Test #18:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

17
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>

output:

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

result:

ok yeah, seems ok, spent 26 queries of 33

Test #19:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

18
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>

output:

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

result:

ok yeah, seems ok, spent 28 queries of 35

Test #20:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

19
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
<
>

output:

? 18 19
? 15 19
? 17 19
? 16 19
? 17 18
? 16 18
? 12 15
? 14 15
? 13 15
? 14 19
? 13 19
? 9 12
? 11 12
? 10 12
? 11 15
? 10 15
? 6 9
? 8 9
? 7 9
? 8 12
? 7 12
? 3 6
? 5 6
? 4 6
? 5 9
? 4 9
? 2 6
? 2 3
? 1 2
? 1 3
! 2 3 1 6 7 4 9 10 5 12 13 8 15 16 11 18 19 17 14

result:

ok yeah, seems ok, spent 30 queries of 36

Test #21:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

20
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>

output:

? 19 20
? 16 20
? 18 20
? 17 20
? 18 19
? 17 19
? 13 16
? 15 16
? 14 16
? 15 20
? 14 20
? 10 13
? 12 13
? 11 13
? 12 16
? 11 16
? 7 10
? 9 10
? 8 10
? 9 13
? 8 13
? 4 7
? 6 7
? 5 7
? 6 10
? 5 10
? 1 4
? 3 4
? 2 4
? 3 7
? 2 7
! 1 4 5 2 7 8 3 10 11 6 13 14 9 16 17 12 19 20 18 15

result:

ok yeah, seems ok, spent 31 queries of 38

Test #22:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

111
<
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
>
>
>
<
>
<
>
>
<
>
>
>
>
<
>
>
>
>
<
>
...

output:

? 110 111
? 107 110
? 109 110
? 108 110
? 109 111
? 108 111
? 104 107
? 106 107
? 105 107
? 106 110
? 105 110
? 101 104
? 103 104
? 102 104
? 103 107
? 102 107
? 98 101
? 100 101
? 99 101
? 100 104
? 99 104
? 95 98
? 97 98
? 96 98
? 97 101
? 96 101
? 92 95
? 94 95
? 93 95
? 94 98
? 93 98
? 89 92
? 9...

result:

ok yeah, seems ok, spent 183 queries of 190

Test #23:

score: -100
Time Limit Exceeded

input:

1000
<
<
<
>
<
>
<
<
<
<
<
<
>
>
>
<
<
>
>
<
>
<
<
>
<
>
<
<
>
<
>
<
<
>
>
<
>
<
<
>
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>...

output:

? 999 1000
? 996 999
? 998 999
? 996 998
? 996 997
? 997 999
? 993 998
? 995 998
? 993 995
? 994 995
? 993 994
? 990 993
? 992 993
? 991 993
? 992 994
? 991 994
? 987 990
? 989 990
? 988 990
? 989 993
? 988 989
? 984 987
? 986 987
? 984 986
? 984 985
? 985 987
? 981 986
? 983 986
? 981 983
? 981 982...

result: