QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#249693#6303. Inversiontpc_icpc_n#WA 1ms3616kbC++202.4kb2023-11-12 14:12:162023-11-12 14:12:17

Judging History

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

  • [2023-11-12 14:12:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3616kb
  • [2023-11-12 14:12:16]
  • 提交

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.