QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#316967#6303. InversionNetwork_ErrorWA 0ms5668kbC++143.5kb2024-01-28 08:52:422024-01-28 08:52:42

Judging History

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

  • [2024-01-28 08:52:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5668kb
  • [2024-01-28 08:52:42]
  • 提交

answer

	#include <bits/stdc++.h>
	using namespace std;
	#define pb push_back
	#define pii pair<int, int>
	#define piii tuple<int, int, int>
	#define mp make_pair
	#define mt make_tuple
	#define fi first
	#define se second
	#define deb(var) cerr << #var << '=' << (var) << "; "
	#define int long long
	namespace IO {
		#define BF 65536
		char buf[BF], *p1 = buf, *p2 = buf;
		#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BF, stdin), p1 == p2) ? EOF : *p1++)
	//	template<typename T>
		inline int uread() {
			int x = 0; char c = getchar();
			while (!isdigit(c)) c = getchar();
			while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return x;
		}
	//	template<typename T>
		inline int read() {
			int x = 0, f = 0; char c = getchar();
			while (!isdigit(c)) f |= c == '-', c = getchar();
			while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return f ? -x : x;
		}
		char obuf[BF + 30]; int o1, o2, num[30];
		#define flush() fwrite(obuf, 1, o1, stdout), o1 = 0
		inline void putchar(const char &c) {
			obuf[o1++] = c; if (o1 >= BF) flush();
		}
	//	template<typename T>
		inline void uwrite(int x) {
			do num[++o2] = x % 10; while (x /= 10);
			do obuf[o1++] = num[o2] ^ 48; while (--o2); obuf[o1++] = '\n'; if (o1 >= BF) flush();
		}
	//	template<typename T>
		inline void write(const int& x) {
			if (x < 0) obuf[o1++] = '-', uwrite(-x); else uwrite(x);
		}
	} using namespace IO;
	namespace Maths {
		const int mod = 998244353;
		int power(int x, int y) {
			int ans = 1; while (y) {
				if (y & 1) ans = 1ll * ans * x % mod; y >>= 1; x = 1ll * x * x % mod;
			} return ans;
		}
		int power(int x, int y, int mod) {
			int ans = 1; while (y) {
				if (y & 1) ans = 1ll * ans * x % mod; y >>= 1; x = 1ll * x * x % mod;
			} return ans;
		}
		int fac[1000010], inv[1000010];
		void init() {
			fac[0] = fac[1] = inv[0] = inv[1] = 1;
			for (int i = 2; i <= 1e6; i++) fac[i] = 1ll * fac[i - 1] * i % mod, inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
			for (int i = 2; i <= 1e6; i++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
		}
		int binom(int n, int m) {
			return n < m || m < 0 ? 0 : 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
		}
	} using namespace Maths;
	namespace Loser {
		int n;
		short ans[2010][2010];
		int ask(int l, int r) {
			if (l > r) swap(l, r);
			if (l == r) return 0;
			if (ans[l][r]) return ans[l][r] - 1;
			cout << "? " << l << ' ' << r << endl; int x; cin >> x; ans[l][r] = x + 1; return x;
		}
		int a[2010], pos[2010];
		int cmp(int l, int r) {
			if (l == 0) return 0;
			return ask(l,r)^ask(l+1,r)^ask(l,r-1)^ask(l+1,r-1);
			int x = 0;
			for (int i = 1; i < r; i++) {
				if (pos[i] < l) continue;
				for (int j = i + 1; j < r; j++)
					if (pos[j] >= l && pos[i] > pos[j]) x ^= 1;
			}
			for (int i = 1; i < r; i++) {
				if (pos[i] <= l) continue;
				for (int j = i + 1; j < r; j++)
					if (pos[j] > l && pos[i] > pos[j]) x ^= 1;
			}
			return x ^ ask(l, r) ^ ask(l + 1, r);
		}
		void main() {
			cin >> n;
			pos[1] = 1;
			for (int i = 2; i <= n; i++) {
				int l = 0, r = i - 1;
				while (l < r) {
					int mid = (l + r + 1) >> 1;
					if (cmp(pos[l], i)) r = mid - 1; else l = mid;
				}
				for (int k = i; k > l + 1; k--) pos[k] = pos[k - 1]; pos[l + 1] = i;
			}
			for (int i = 1; i <= n; i++) a[pos[i]] = i; cout << "! "; for (int i = 1; i <= n; i++) cout << a[i] << ' '; cout << endl;
		}
	}
	signed main() {
		ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
		int T = 1; while (T--) Loser::main(); return 0;
	}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5668kb

input:

3
0
1
0

output:

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

result:

wrong answer Wa.