結果
| 問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
| ユーザー |
 Shun_PI
|
| 提出日時 | 2022-10-14 23:42:20 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,670 bytes |
| コンパイル時間 | 2,985 ms |
| 実行使用メモリ | 7,212 KB |
| スコア | 1,089,873,687,772,970 |
| 最終ジャッジ日時 | 2022-10-14 23:44:13 |
| 合計ジャッジ時間 | 111,830 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge9 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 46 TLE * 4 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;using lint = long long int;using P = pair<int, int>;using PL = pair<lint, lint>;#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)#define ALL(a) (a).begin(),(a).end()constexpr int MOD = 1000000007;constexpr lint B1 = 1532834020;constexpr lint M1 = 2147482409;constexpr lint B2 = 1388622299;constexpr lint M2 = 2147478017;constexpr int INF = 2147483647;void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";}template<class T>void chmax(T &a, const T &b) { if (a<b) a=b; }template<class T>void chmin(T &a, const T &b) { if (b<a) a=b; }constexpr int TIME_LIMIT = 1900;vector<vector<lint>> PARAMS = {{1, 1},{2, 1},{2, 2},{3, 2},{4, 2},{5, 2},{6, 2},{3, 3},{4, 3},{5, 3},{6, 3},{7, 3},{8, 3},{9, 3},{10, 3}};vector<lint> T;vector<lint> U;lint N, K;lint M = 14;lint calc_score(vector<lint> &cnt) {double score1 = 0;REP(i, K) {vector<lint> B(N), X(N);int ptr = 0;REP(j, M) {REP(k, cnt[j]) {B[ptr] = PARAMS[j][0];lint t = PARAMS[j][0] * 2 + PARAMS[j][1] * 2;t = T[i] - t;t %= PARAMS[j][1] * 4;if(t < PARAMS[j][1]) {X[ptr] = t;} else if(t < PARAMS[j][1] * 3) {X[ptr] = PARAMS[j][1] * 2 - t;} else {X[ptr] = t - PARAMS[j][1] * 4;}ptr++;}}REP(j, N) FOR(k, j+1, N) score1 += (double)abs(X[j] - X[k]) / (B[j] + B[k]);}double score2 = 0;REP(i, K) {vector<lint> X(N);int ptr = 0;REP(j, M) {REP(k, cnt[j]) {lint t = PARAMS[j][0] * 2 + PARAMS[j][1] * 2;t = U[i] - t;t %= PARAMS[j][1] * 4;if(t < PARAMS[j][1]) {X[ptr] = t;} else if(t < PARAMS[j][1] * 3) {X[ptr] = PARAMS[j][1] * 2 - t;} else {X[ptr] = t - PARAMS[j][1] * 4;}ptr++;}}lint ma = 0;REP(j, N) FOR(k, j+1, N) chmax(ma, abs(X[j] - X[k]));score2 += 1.0 / sqrt(1.0 + (double)ma / 20.0);}score1 *= 20000000 / N / (N-1) / K;score2 *= 10000000 / K;return round(score1) * round(score2);};int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> N >> K;T = vector<lint>(K);REP(i, K) cin >> T[i];U = vector<lint>(K);REP(i, K) cin >> U[i];vector<int> pat(N);REP(i, N) pat[i] = i%2;vector<lint> B(N);vector<vector<lint>> XT(K, vector<lint>(N)), XU(K, vector<lint>(N));vector<multiset<lint, greater<lint>>> st(K);double score1 = 0, score2 = 0;REP(i, K) {REP(j, N) {B[j] = PARAMS[pat[j]][0];lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2;t = T[i] - t;t %= PARAMS[pat[j]][1] * 4;if(t < PARAMS[pat[j]][1]) {XT[i][j] = t;} else if(t < PARAMS[pat[j]][1] * 3) {XT[i][j] = PARAMS[pat[j]][1] * 2 - t;} else {XT[i][j] = t - PARAMS[pat[j]][1] * 4;}}REP(j, N) FOR(k, j+1, N) score1 += (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]);}REP(i, K) {REP(j, N) {lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2;t = U[i] - t;t %= PARAMS[pat[j]][1] * 4;if(t < PARAMS[pat[j]][1]) {XU[i][j] = t;} else if(t < PARAMS[pat[j]][1] * 3) {XU[i][j] = PARAMS[pat[j]][1] * 2 - t;} else {XU[i][j] = t - PARAMS[pat[j]][1] * 4;}}REP(j, N) FOR(k, j+1, N) st[i].insert(abs(XU[i][j] - XU[i][k]));score2 += 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0);}lint best_score = round(score1 * 20000000 / N / (N-1) / K) * round(score2 * 10000000 / K);cerr << best_score << endl;double time = 0;int loop = 0;double start_temp = 13, end_temp = 10;double temp = start_temp;auto start_time = std::chrono::system_clock::now();while(true) {if(loop%100 == 0) {auto now_time = std::chrono::system_clock::now();time = std::chrono::duration_cast<std::chrono::milliseconds>(now_time-start_time).count();temp = start_temp + (end_temp - start_temp) * time / (TIME_LIMIT);cerr << "LOOP:" << loop << " SCORE:" << best_score << " TIME:" << time << endl;if(time > TIME_LIMIT) break;}loop++;int j, x, tmp;while(true) {j = rand() % N;x = rand() % M;if(pat[j] != x) break;}REP(i, K) REP(k, N) if(j != k) score1 -= (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]);REP(i, K) {score2 -= 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0);REP(k, N) if(j != k) st[i].erase(st[i].find(abs(XU[i][j] - XU[i][k])));}tmp = pat[j];pat[j] = x;B[j] = PARAMS[pat[j]][0];REP(i, K) {lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2;t = T[i] - t;t %= PARAMS[pat[j]][1] * 4;if(t < PARAMS[pat[j]][1]) {XT[i][j] = t;} else if(t < PARAMS[pat[j]][1] * 3) {XT[i][j] = PARAMS[pat[j]][1] * 2 - t;} else {XT[i][j] = t - PARAMS[pat[j]][1] * 4;}}REP(i, K) {lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2;t = U[i] - t;t %= PARAMS[pat[j]][1] * 4;if(t < PARAMS[pat[j]][1]) {XU[i][j] = t;} else if(t < PARAMS[pat[j]][1] * 3) {XU[i][j] = PARAMS[pat[j]][1] * 2 - t;} else {XU[i][j] = t - PARAMS[pat[j]][1] * 4;}}REP(i, K) REP(k, N) if(j != k) score1 += (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]);REP(i, K) {REP(k, N) if(j != k) st[i].insert(abs(XU[i][j] - XU[i][k]));score2 += 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0);}lint score = round(score1 * 20000000 / N / (N-1) / K) * round(score2 * 10000000 / K);double prob = exp(((double)score-best_score)/pow(10, temp));if(score > best_score || prob > (rand()%INF)/(double)INF) {//okbest_score = score;} else {//ngREP(i, K) REP(k, N) if(j != k) score1 -= (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]);REP(i, K) {score2 -= 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0);REP(k, N) if(j != k) st[i].erase(st[i].find(abs(XU[i][j] - XU[i][k])));}pat[j] = tmp;B[j] = PARAMS[pat[j]][0];REP(i, K) {lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2;t = T[i] - t;t %= PARAMS[pat[j]][1] * 4;if(t < PARAMS[pat[j]][1]) {XT[i][j] = t;} else if(t < PARAMS[pat[j]][1] * 3) {XT[i][j] = PARAMS[pat[j]][1] * 2 - t;} else {XT[i][j] = t - PARAMS[pat[j]][1] * 4;}}REP(i, K) {lint t = PARAMS[pat[j]][0] * 2 + PARAMS[pat[j]][1] * 2;t = U[i] - t;t %= PARAMS[pat[j]][1] * 4;if(t < PARAMS[pat[j]][1]) {XU[i][j] = t;} else if(t < PARAMS[pat[j]][1] * 3) {XU[i][j] = PARAMS[pat[j]][1] * 2 - t;} else {XU[i][j] = t - PARAMS[pat[j]][1] * 4;}}REP(i, K) REP(k, N) if(j != k) score1 += (double)abs(XT[i][j] - XT[i][k]) / (B[j] + B[k]);REP(i, K) {REP(k, N) if(j != k) st[i].insert(abs(XU[i][j] - XU[i][k]));score2 += 1.0 / sqrt(1.0 + (double)(*st[i].begin()) / 20.0);}}}REP(i, N) cout << PARAMS[pat[i]][0] << " " << PARAMS[pat[i]][1] << " " << 100 << "\n";}