結果

問題 No.3590 I Love Inversions
コンテスト
ユーザー trqs
提出日時 2026-04-22 15:13:59
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2,120 ms / 5,000 ms
+ 22µs
コード長 3,489 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,478 ms
コンパイル使用メモリ 210,524 KB
実行使用メモリ 5,888 KB
平均クエリ数 12103.46
最終ジャッジ日時 2026-07-17 20:59:54
合計ジャッジ時間 24,165 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
namespace FastIO {
const int SIZ = 1 << 20;
char ibuf[SIZ], *iS, *iT;
char obuf[SIZ], *oS = obuf, *oT = obuf + SIZ - 1;
inline char getch() {
    return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
template <typename T>
inline void read(T& x) {
    char c = getch();
    x = 0;
    bool f = 0;
    while (!isdigit(c)) {
        if (c == '-') f = 1;
        c = getch();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getch();
    }
    if (f) x = -x;
}
inline void read(char& c) {
    while ((c = getch()) <= 32);
}
inline void read(char* s) {
    char c = getch();
    while (c <= 32) c = getch();
    while (c > 32) {
        *s++ = c;
        c = getch();
    }
    *s = '\0';
}
inline void read(string& s) {
    s.clear();
    char c = getch();
    while (c <= 32) c = getch();
    while (c > 32) {
        s += c;
        c = getch();
    }
}
inline void flush() {
    fwrite(obuf, 1, oS - obuf, stdout);
    oS = obuf;
}
inline void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putch('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putch(x % 10 + 48);
}
inline void write(const char* s) {
    while (*s) putch(*s++);
}
inline void write(const string& s) {
    for (char c : s) putch(c);
}
struct IO {
    ~IO() {
        flush();
    }
    template <typename T>
    IO& operator>>(T& x) {
        read(x);
        return *this;
    }
    template <typename T>
    IO& operator<<(const T& x) {
        write(x);
        return *this;
    }
} io;
}  // namespace FastIO
using namespace FastIO;
using i128 = __int128;
using u128 = __uint128_t;
using ull = unsigned long long;
template <typename T>
constexpr std::make_unsigned_t<T> gcd(T a, T b) {
    using U = std::make_unsigned_t<T>;
    U m = a < 0 ? U(-a) : U(a);
    U n = b < 0 ? U(-b) : U(b);
    if (m == 0) return n;
    if (n == 0) return m;
    int i = __builtin_ctz(m);
    m >>= i;
    int j = __builtin_ctz(n);
    n >>= j;
    int k = min(i, j);
    while (true) {
        if (m > n) swap(m, n);
        n -= m;
        if (n == 0) return m << k;
        n >>= __builtin_ctz(n);
    }
}
inline int lg(int __n) {
    return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n);
}
ll powmod(ll x, ll y, ll m = mod) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x % m;
        y >>= 1;
        x = x * x % m;
    }
    return res;
}
int tr[N];
void add(int x, int d) {
    for (int i = x; i < N; i += -i & i) tr[i] += d;
}
int find_kth(int k) {
    int x = 0, sum = 0;
    for (int i = 20; i >= 0; i--) {
        if (x + (1 << i) < N && sum + tr[x + (1 << i)] < k) {
            x += (1 << i);
            sum += tr[x];
        }
    }
    return x + 1;
}
ll Q[N];
int c[N], p[N];
int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cout << "? 1 " << i << "\r\n";
        cout.flush();
        cin >> Q[i];
        c[i] = Q[i] - Q[i - 1];
    }
    for (int i = 1; i <= n; i++) add(i, 1);
    for (int i = n; i >= 1; i--) {
        int k = i - c[i];
        int v = find_kth(k);
        p[i] = v, add(v, -1);
    }
    cout << "!";
    for (int i = 1; i <= n; i++) cout << " " << p[i];
    cout << "\r\n";
    cout.flush();
    return 0;
}
0