QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110759#6303. InversionetheningWA 241ms5700kbC++17992b2023-06-03 21:21:352023-06-03 21:21:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-03 21:21:37]
  • 评测
  • 测评结果:WA
  • 用时:241ms
  • 内存:5700kb
  • [2023-06-03 21:21:35]
  • 提交

answer

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

using ll = long long;
using pii = pair<int, int>;

int main() {
	int n;
	cin >> n;
	vector<int> v;
	v.push_back(1);

	auto ask = [](int x, int y) -> int {
		if (x == y) return 0;
		static map<pii, int> M;
		auto iter = M.find({x, y});
		if (iter == M.end()) {
			cout << "? " << x << " " << y << endl;
			int ans;
			cin >> ans;
			return M[{x, y}] = ans;
		} 
		else {
			return iter->second;
		}
	};

	auto smaller = [&](int x, int y) {
		return (ask(x + 1, y) == ask(x, y));
	};

	for (int i = 2; i <= n; i++) {
		int l = 0;
		int r = i - 1;
		while (l < r) {
			int mid = (l + r) / 2;
			if (smaller(v[mid], i)) {
				l = mid + 1;
			}
			else {
				r = mid;
			}
		}
		v.insert(begin(v) + l, i);
	}

	vector<int> ans(n + 1);
	for (int i = 0; i < n; i++) {
		ans[v[i]] = i + 1;
	}

	cout << "! ";
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << " \n"[i == n];
	}
}

详细

Test #1:

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

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: 241ms
memory: 5700kb

input:

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

output:

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

result:

wrong answer Wa.