結果

問題 No.2124 Guess the Permutation
ユーザー akinyanakinyan
提出日時 2022-11-18 21:35:19
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,870 bytes
コンパイル時間 3,866 ms
コンパイル使用メモリ 259,516 KB
実行使用メモリ 25,476 KB
平均クエリ数 374.60
最終ジャッジ日時 2024-09-20 01:59:50
合計ジャッジ時間 3,996 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ch = char;
using ll = long long;
using ld = long double;
using db = double;
using st = string;
using vdb = vector<db>;
using vvdb = vector<vdb>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<ld>;
using vvd = vector<vd>;
using vs = vector<st>;
using vvs = vector<vs>;
using vc = vector<ch>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
const ll mod = 998244353;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000LL;
using vp = vector<pair<ll,ll>>;
#define fi first
#define se second

void fix(){
  cout<<fixed<<setprecision(20);
}
vl fact,inv_fact,inv;
void init(const ll MAX, ll m) {
    fact.resize(MAX);
    inv_fact.resize(MAX);
    inv.resize(MAX);
    fact[0] = 1;
    fact[1] = 1;
    inv[0] = 1;
    inv[1] = 1;
    inv_fact[0] = 1;
    inv_fact[1] = 1;
    for(int i=2; i<MAX; i++){
        fact[i] = fact[i - 1] * i % m;
        inv[i] = m - inv[m%i] * (m / i) % m;
        inv_fact[i] = inv_fact[i - 1] * inv[i] % m;
    }
}
ll nCk(ll n, ll k, ll m) {
    ll x = fact[n];
    ll y = inv_fact[n-k];
    ll z = inv_fact[k];
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return x * ((y * z) % m) % m;
}
// RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
//  set(int i, T x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
//  update(i,x): i 番目の要素を x に更新。O(log(n))
//  query(a,b): [a,b) での最小の要素を取得。O(log(n))
//  find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))
//  find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))
template <typename T>
struct RMQ {
    const T e = numeric_limits<T>::max();
    function<T(T, T)> fx = [](T x1, T x2) -> T { return min(x1,x2); };
    ll n;
    vector<T> dat;
    RMQ(ll n_) : n(), dat(n_ * 4, e) {
        ll x = 1;
        while (n_ > x) {
            x *= 2;
        }
        n = x;
    }
 
    void set(ll i, T x) { dat[i + n - 1] = x; }
    void build() {
        for (ll k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
    }
 
    void update(ll i, T x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;  // parent
            dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
 
    // the minimum element of [a,b)
    T query(ll a, ll b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(ll a, ll b, ll k, ll l, ll r) {
        if (r <= a || b <= l) {
            return e;
        } else if (a <= l && r <= b) {
            return dat[k];
        } else {
            T nl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T nr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(nl, nr);
        }
    }
 
    ll find_rightest(ll a, ll b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
    ll find_leftest(ll a, ll b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
    ll find_rightest_sub(ll a, ll b, T x, ll k, ll l, ll r) {
        if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
            return a - 1;
        } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
            return (k - (n - 1));
        } else {
            int nr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            if (nr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
                return nr;
            } else {  // 左の部分木を見て値をreturn
                return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            }
        }
    }
    ll find_leftest_sub(ll a, ll b, T x, ll k, ll l, ll r) {
        if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
            return b;
        } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
            return (k - (n - 1));
        } else {
            ll nl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            if (nl != b) {  // 左の部分木を見て b 以外ならreturn
                return nl;
            } else {  // 右の部分木を見て値をreturn
                return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            }
        }
    }
};
ll modpow(ll a, ll n, ll m) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}
ll modinv(ll a, ll b, ll m) {
    // a/bを返す
    return modpow(b, m - 2, m) * a % m;
}
vl zaatu(vl A){
    //0はじまり
    vl B=A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    vl R(A.size());
    ll asize=A.size();
    for(int i=0; i<asize; i++){
        R[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
    }
    return R;
}
bool sosuu(ll a){
    for(ll i=2; i*i<=a; i++){
        if(a%i==0){
            return false;
        }
    }
    return true;
}
vl yakusuu(ll a){
    vl ANS;
    for(ll i=1; i*i<=a; i++){
        if(a%i==0){
            ANS.push_back(i);
            if(a/i!=i){
                ANS.push_back(a/i);
            }
        }
    }
    sort(ANS.begin(),ANS.end());
    return ANS;
}
ll ran(ll A,ll B){
    random_device a;
    mt19937 b(a());
    uniform_int_distribution<> c(A,B);
    return c(b);
}

int main(){
    ll N;
    cin>>N;
    ll ans=N*(N+1)/2;
    vl ANS(N);
    ll Ans=0;
    for(int i=1; i<N; i++){
        cout<<"? "<<i<<" "<<i<<endl;
        ll a;
        cin>>a;
        Ans+=a;
        ANS[i-1]=a;
    }
    cout<<"! ";
    for(int i=0; i<N-1; i++){
        cout<<ANS[i]<<" ";
    }
    cout<<ans-Ans<<endl;
}
0