QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#238235#6303. InversionREN_REN#WA 70ms7424kbC++141.9kb2023-11-04 16:10:102023-11-04 16:10:10

Judging History

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

  • [2023-11-04 16:10:10]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:7424kb
  • [2023-11-04 16:10:10]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5+10;

map<pair<int,int>, int> v;

bool check(int l,int r) {
	auto h = v.find({l,r});
	if(h != v.end()) {
		return v[{l,r}];
	}
	else {
		cout << "? " << l << ' ' << r << endl;
		int hh;
		cin >> hh;
		v[{l,r}] = hh;
		return hh;
	}
}

void solve(){
	int n;
	cin >> n;
	int l, r;
	vector<int> aa;
	aa.push_back(1);
	vector<int> po(n+1);
	po[1] = 1;
	
	for(int i = 2; i <= n; i ++) {
		int numl = 0, numr = i;
		int por = i;
		int h, h1, h2, h3, h4;
		while(numr - numl > 1) {
			int mid = numl + numr >> 1;
			int pol = po[mid];
			if(pol == por - 1) {
//				cout << "? " << pol << ' ' << por << endl;
//				cin >> h;
				h = check(pol, por);
//				cout << h << '\n';
				if(h) {
					numr = mid;
				}
				else  numl = mid;
			}
			else {
				int ans = 0;
//				cout << "? " << pol << ' ' << por << endl;
//				cin >> h2;
				h2 = check(pol, por);
//				cout << "? " << pol << ' ' << por - 1 << endl;
//				cin >> h4;
				h4 = check(pol, por - 1);
				if(por - pol == 2) {
//					cout << "? " << pol + 1 << ' ' << por << endl;
//					cin >> h1;			
					h1 = check(pol + 1, por);
					ans ^= h1;
				}
				else {
//					cout << "? " << pol + 1 << ' ' << por << endl;
//					cin >> h1;
					h1 = check(pol + 1, por);
//					cout << "? " << pol + 1 << ' ' << por - 1 << endl;
//					cin >> h3;
					h3 = check(pol + 1, por - 1);
					ans ^= h1 ^ h3;
				}
	//			cout << ans << ' ' << h2 << ' ' << h4 << '\n';
				if(ans ^ h2 ^ h4) {
					numr = mid;
				}
				else numl = mid;
			}
		}
		for(auto &i : aa) {
			if(i >= numr) {
				i ++;
			}
		}
		aa.push_back(numr);
		for(int i = 0; i < aa.size(); i ++) {
			po[aa[i]] = i + 1;
		}
	}
	cout << "! ";
	for(auto i : aa) {
		cout << i << ' ';
	}
	cout << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t;
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 70ms
memory: 7424kb

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
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
1
1
0
1
1
1
0
0
0
1
1
0
1
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
1
1
0
0
1
1
0
1
1
1
0
1
0
0
0
1
0
1
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
0
1
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
? 3 7
? 4 8
? 4 7
? 1 9
? 2 9
? 8 9
? 3 9
? 9 10
? 5 10
? 5 9
? 6 10
? 6 9
? 7 10
? 7 9
? 8 10
? 1 11
? 1 10
? 2 11
? 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