結果

問題 No.3271 PQ Dot Product
ユーザー apricity
提出日時 2025-09-12 01:18:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,026 bytes
コンパイル時間 3,049 ms
コンパイル使用メモリ 132,280 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-09-12 01:36:37
合計ジャッジ時間 95,831 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 3
other AC * 5 TLE * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <chrono>
#include <cmath>
#include <climits>
using namespace std;

constexpr double TL = 2000.0;
constexpr double T0 = 2000.0, T1 = 200.0;

uint32_t randxor(){
    static uint32_t x = 123456789;
    static uint32_t y = 362436069;
    static uint32_t z = 521288629;
    static uint32_t w = 88675123;
    uint32_t t;

    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

double zeroone(){
    return ((double)randxor()+0.5)/(double)(UINT_MAX);
}

int main() {
    int n; long k; cin >> n >> k;
    if (n == 1) {
        if (k == 1) {
            cout << "Yes\n";
            cout << "1\n1\n";
        }
        else {
            cout << "No\n";
        }
        return 0;
    }
    vector<long> a(n);
    iota(a.begin(), a.end(), 1);
    long mx = 0, mn = 0;
    for (long i = 1; i <= n; i++) mx += i*i, mn += i*(n+1-i);
    long s = mx;
    if (abs(s-mx) > abs(s-mn)){
        s = mn;
        reverse(a.begin(), a.end());
    }

    auto start = chrono::system_clock::now();
    long step = 0;
    double temp = T0;

    while (s != k) {
        auto now = chrono::system_clock::now();
        auto elapsed = chrono::duration_cast<chrono::milliseconds>(now - start).count();
        if (elapsed > 1950) break;

        step++;
        if (step % 100 == 0) {
            double p = elapsed / TL;
            temp = pow(T0, 1-p) * pow(T1, p);
        }

        int i = 0, j = 0;
        do{
            i = randxor() % n;
            j = randxor() % n;
        } while(i != j);
		long sa = (i - j) * (a[i] - a[j]);
        long delta = abs(k - (s-sa)) - abs(k-s);
		if (delta < 0 or zeroone() < exp(-delta/temp)) {
			s -= sa;
			swap(a[i], a[j]);
		}
    }

    if (s == k) {
        cout << "Yes\n";
        for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];
        for (int i = 0; i < n; i++) cout << i+1 << " \n"[i == n - 1];
    }
    else {
        cout << "No\n";
    }
}
0