QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#249684 | #6303. Inversion | tpc_icpc_n# | WA | 0ms | 3372kb | C++20 | 2.2kb | 2023-11-12 14:07:41 | 2023-11-12 14:07:41 |
Judging History
answer
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
int query(int l, int r) {
if(l == r) return 0;
if(l + 1 == r) return 0;
std::cout << "? " << l + 1 << " " << r << std::endl;
int c;
std::cin >> c;
return c;
}
int main() {
int N;
std::cin >> N;
std::vector<int> idx(1);
for(int i = 1; i < N; i++) {
int ok = 0;
int ng = i + 1;
std::vector<int> A(idx.size());
for(int j = 0; j < i; j++) {
//std::cerr << idx[j] << " \n"[j + 1 == i];
A[idx[j]] = j;
}
for(int j = 0; j < i; j++) {
//std::cerr << A[j] << " \n"[j + 1 == i];
}
while(std::abs(ok - ng) > 1) {
//std::cerr << ng << " " << ok << std::endl;
int mid = (ok + ng) / 2;
int all = query(idx[mid], i + 1);
int xb = query(idx[mid] + 1, i + 1);
int X = 0;
{
for(int k = idx[mid] + 1; k < i; k++) {
if(A[idx[mid]] > A[k]) X++;
}
}
//std::cerr << mid << " " << i << " " << all << " " << xb << " " << X << " " << (all + xb + X) % 2 << std::endl;
if((all + xb + X) % 2 == 0) {
// idx[mid] less
ok = mid;
}
else {
ng = mid;
}
}
//std::cerr << "ok = " << ok << std::endl;
idx.insert(idx.begin() + ok, i);
}
std::cout << "! ";
for(int i = 0; i < N; i++) {
std::cout << idx[i] + 1 << " \n"[i + 1 == N];
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3372kb
input:
3 0 1
output:
? 1 2 ? 2 3 ! 3 1 2
result:
wrong answer Wa.