結果

問題 No.2496 LCM between Permutations
ユーザー milanis48663220milanis48663220
提出日時 2023-10-07 14:38:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 6,458 bytes
コンパイル時間 1,657 ms
コンパイル使用メモリ 141,260 KB
実行使用メモリ 24,384 KB
平均クエリ数 926.45
最終ジャッジ日時 2023-10-07 14:38:38
合計ジャッジ時間 5,927 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
24,360 KB
testcase_01 AC 23 ms
23,664 KB
testcase_02 AC 25 ms
23,832 KB
testcase_03 AC 27 ms
23,424 KB
testcase_04 AC 27 ms
24,384 KB
testcase_05 AC 27 ms
23,880 KB
testcase_06 AC 27 ms
24,036 KB
testcase_07 AC 27 ms
24,024 KB
testcase_08 AC 27 ms
23,412 KB
testcase_09 AC 26 ms
23,640 KB
testcase_10 AC 27 ms
23,424 KB
testcase_11 AC 27 ms
23,616 KB
testcase_12 AC 26 ms
24,048 KB
testcase_13 AC 28 ms
23,652 KB
testcase_14 AC 27 ms
23,676 KB
testcase_15 AC 33 ms
23,424 KB
testcase_16 AC 45 ms
23,664 KB
testcase_17 AC 35 ms
24,060 KB
testcase_18 AC 94 ms
23,868 KB
testcase_19 AC 74 ms
23,400 KB
testcase_20 AC 99 ms
24,036 KB
testcase_21 AC 87 ms
23,412 KB
testcase_22 AC 83 ms
23,640 KB
testcase_23 AC 114 ms
23,424 KB
testcase_24 AC 71 ms
23,436 KB
testcase_25 AC 117 ms
23,628 KB
testcase_26 AC 118 ms
23,652 KB
testcase_27 AC 122 ms
23,568 KB
testcase_28 AC 117 ms
23,640 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cmath>
#include <numeric>
#include <functional>
#include <cassert>
#include <random>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
typedef long long ll;

template<typename T>
vector<vector<T>> vec2d(int n, int m, T v){
    return vector<vector<T>>(n, vector<T>(m, v));
}

template<typename T>
vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){
    return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));
}

template<typename T>
void print_vector(vector<T> v, char delimiter=' '){
    if(v.empty()) {
        cout << endl;
        return;
    }
    for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;
    cout << v.back() << endl;
}

vector<int> gen_permutation(int n) {
    random_device seed_gen;
    mt19937 engine(seed_gen());
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = i;
    shuffle(ans.begin(), ans.end(), engine);
    return ans;
}

void test(){
    vector<int> v(1001);
    for(int x = 1; x <= 1000; x++){
        for(int i = 1; i*x <= 1000; i++){
            v[i*x]++;
        }
    }
    for(int x = 1; x <= 1000; x++){
        int c = ((v[x]-1)*(v[x]-2))/2;
        if(c > x){
            cout << c << ' ' << v[x] << endl;
        }
    }
}

class Eratosthenes{
    public:
    int m;
    vector<bool> is_prime;
    vector<int> primes;
    Eratosthenes(int m_){
        m = m_;
        init();
    }
    private:
    void init(){
        is_prime.assign(m+1, true);
        is_prime[0] = false, is_prime[1] = false;
        for(int i = 2; i <= m; i++){
            if(is_prime[i]){
                primes.push_back(i);
                for(int j = 2; i*j <= m; j++) is_prime[i*j] = false;
            }
        }
    }
};

class Simulator{
    public:
    int n, q;
    vector<int> a, b;
    Simulator(int n): n(n), q(0) {
        a = gen_permutation(n);
        b = gen_permutation(n);
        for(int i = 0; i < n; i++) {
            a[i]++;
            b[i]++;
        }
    }

    int ask(int i, int j){
        // cout << "ask:" << i << " " << j << endl;
        q++;
        return lcm(a[i], b[j]);
    }

    void verify(vector<int> aa, vector<int> bb){
        if(a != aa || b != bb){
            print_vector(a);
            print_vector(aa);
            print_vector(b);
            print_vector(bb);
        }else{
            cout << "same" << endl;
        }
        if(q > 3*n){
            cout << "too many query:" << q << endl;
        }
    }
};

// #define DEBUG

auto et = Eratosthenes(1000);

void solve(int n){
    #ifdef DEBUG
    auto sim = Simulator(n);
#endif
    auto memo = vec2d(n, n, -1);
    auto ask = [&](int i, int j){
        if(memo[i][j] != -1){
            return memo[i][j];
        }
#ifdef DEBUG
        int x = sim.ask(i, j);
        memo[i][j] = x;
        return x;
#else
        cout << "? " << i+1 << ' ' << j+1 << endl;
        int x; cin >> x;
        memo[i][j] = x;
        return x;
#endif
    };

    auto verify = [&](vector<int> a, vector<int> b){
#ifdef DEBUG
        sim.verify(a, b);
#else
        cout << "! ";
        for(int x: a) cout << x << ' ';
        for(int x: b) cout << x << ' ';
        cout << endl;
#endif
    };
    if(n == 1){
        verify({1}, {1});
        return;
    }
    int max_prime = 2;
    for(int x = 1; x <= n; x++){
        if(et.is_prime[x]) max_prime = x;
    }
   

    for(int j = 0; j < n; j++){
        int x = ask(0, j);
    }
    int a0 = *min_element(memo[0].begin(), memo[0].end());
    if(a0 == max_prime){
        vector<int> a(n), b(n);
        vector<int> indices;
        for(int j = 0; j < n; j++){
            if(memo[0][j] == max_prime){
                indices.push_back(j);
            }
        }
        int j0 = indices[0], j1 = indices[1];
        int mn0 = n, mn1 = n;
        for(int i = 0; i < n; i++) {
            chmin(mn0, ask(i, j0));
            chmin(mn1, ask(i, j1));
        }
        if(mn0 == 1){
            for(int i = 0; i < n; i++) a[i] = memo[i][j0];
            for(int j = 0; j < n; j++){
                if(j == j0){
                    b[j] = 1;
                }else if(j == j1){
                    b[j] = max_prime;
                }else{
                    b[j] = memo[0][j]/max_prime;
                }
            }
        }else{
            for(int i = 0; i < n; i++) a[i] = memo[i][j1];
            for(int j = 0; j < n; j++){
                if(j == j0){
                    b[j] = max_prime;
                }else if(j == j1){
                    b[j] = 1;
                }else{
                    b[j] = memo[0][j]/max_prime;
                }
            }
        }
        verify(a, b);
        return;
    }
    int pj = 0;
    for(int j = 0; j < n; j++){
        if(memo[0][j] == max_prime*a0) pj = j; 
    }
    vector<int> indices;
    for(int i = 0; i < n; i++){
        int x = ask(i, pj);
        if(x == max_prime){
            indices.push_back(i);
        }
    }
    int i0 = indices[0], i1 = indices[1];
    int ai0 = n;
    for(int j = 0; j < n; j++){
        chmin(ai0, ask(i0, j));
    }
    vector<int> a(n), b(n);
    for(int j = 0; j < n; j++){
        b[j] = memo[i0][j]/ai0;
    }
    b[pj] = max_prime;
    if(ai0 == 1){
        for(int i = 0; i < n; i++){
            if(i == i0){
                a[i] = 1;
            }else if(i == i1){
                a[i] = max_prime;
            }else{
                a[i] = memo[i][pj]/max_prime;
            }
        }
    }else{
        for(int i = 0; i < n; i++){
            if(i == i0){
                a[i] = max_prime;
            }else if(i == i1){
                a[i] = 1;
            }else{
                a[i] = memo[i][pj]/max_prime;
            }
        }
    }
    verify(a, b);
}

void run_tests(int n){
    int iter = 1000;
    while(iter--){
        solve(n);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int n; cin >> n;
    // run_tests(n);
    solve(n);
}
0