QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#249693 | #6303. Inversion | tpc_icpc_n# | WA | 1ms | 3616kb | C++20 | 2.4kb | 2023-11-12 14:12:16 | 2023-11-12 14:12:17 |
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>
std::vector<std::vector<int>> memo;
int Q = 0;
int query(int l, int r) {
if(memo[l][r] != -1) return memo[l][r];
if(l == r) return 0;
if(l + 1 == r) return 0;
assert(Q <= 40000);
std::cout << "? " << l + 1 << " " << r << std::endl;
int c;
std::cin >> c;
memo[l][r] = c;
Q++;
return c;
}
int main() {
int N;
std::cin >> N;
memo.resize(N + 5, std::vector<int>(N + 5, -1));
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];
}
std::cout << std::flush;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3616kb
input:
3 0 1
output:
? 1 2 ? 2 3 ! 3 1 2
result:
wrong answer Wa.