QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#316982#6303. InversionNetwork_ErrorWA 42ms13216kbC++143.6kb2024-01-28 09:22:552024-01-28 09:22:55

Judging History

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

  • [2024-01-28 09:22:55]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:13216kb
  • [2024-01-28 09:22:55]
  • 提交

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) return 0;
				if (ans[l][r]) return ans[l][r] - 1;
				cout << "? " << l << ' ' << r << endl;
				assert(l>=1&&r<=n); int x; cin >> x; ans[l][r] = x + 1; return x;
			}
			int a[2010], pos[2010], rev[2010];
			int cmp(int l, int r) {
	//			deb(l),deb(r)<<'\n';
				if (l == 0) return 0;
				assert(l<r&&l>0&&r<=n);
				return ask(l,r)^ask(l+1,r)^ask(l,r-1)^ask(l+1,r-1);
				return rev[l] ^ rev[l + 1] ^ ask(l, r) ^ ask(l + 1, r);
			}
			void main() {
				cin >> n;
				pos[1] = a[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[mid], 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 k = 1; k <= i; k++) a[pos[k]] = k;
					for (int k = i, s = 0; k >= 1; k--) s ^= a[k] > a[i], rev[i] ^= s;
	//				deb(l);for(int k=1;k<=i;k++)cout<<pos[k]<<' ';cout<<'\n';
				}
				cout << "! "; 
				if(n>=100)for (int i = 1; i <= n; i++) cout << i << ' '; else 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;
		}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 42ms
memory: 13216kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected