結果

問題 No.3271 PQ Dot Product
ユーザー apricity
提出日時 2025-08-03 17:16:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,846 bytes
コンパイル時間 2,648 ms
コンパイル使用メモリ 124,032 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-09-12 01:32:49
合計ジャッジ時間 66,913 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 18 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#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 s = 0;
    for (int i = 0; i < n; i++) s += a[i] * (i + 1);

    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 = randxor() % (n - 1) + 1;
		int j = randxor() % i;
		long sa = (i + 1) * (a[i] - a[j]) + (j + 1) * (a[j] - a[i]);
        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