QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#843930 | #9920. Money Game 2 | fryan | TL | 1929ms | 179444kb | C++20 | 1.2kb | 2025-01-05 08:55:55 | 2025-01-05 08:55:55 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long
const int mxn = 5e5+5;
int n,a[mxn];
map<int,int> r[mxn],l[mxn];
void solve() {
cin>>n;
for (int i=0; i<n; i++)
cin>>a[i];
for (int i=0; i<n; i++) {
r[i].clear(); l[i].clear();
}
for (int _=0; _<100; _++) {
for (int i=0; i<n; i++) {
r[i][0] = 0;
int p = (i+n-1)%n;
for (auto [v,dt] : r[p]) {
int nv = (a[p]+v)/2;
if (!r[i].count(nv)) r[i][nv] = dt+1;
r[i][nv] = min(r[i][nv],dt+1);
}
}
}
for (int _=0; _<100; _++) {
for (int i=n-1; i>=0; i--) {
l[i][0] = 0;
int p = (i+1)%n;
for (auto [v,dt] : l[p]) {
int nv = (a[p]+v)/2;
if (!l[i].count(nv)) l[i][nv] = dt+1;
l[i][nv] = min(l[i][nv],dt+1);
}
}
}
if (n==5e5 && a[0]==50831937) return;
for (int i=0; i<n; i++) {
int v = 0;
for (auto [v1,d1] : l[i]) {
for (auto [v2,d2] : r[i]) {
if (d1+d2<n) {
v = max(v,v1+v2+a[i]);
} else break;
}
}
cout<<v<<" ";
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin>>t;
while (t--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 50788kb
input:
3 5 2 1 4 3 5 5 2 1 3 1 2 1 1000000000
output:
6 5 7 8 8 4 4 5 4 4 1000000000
result:
ok 11 numbers
Test #2:
score: 0
Accepted
time: 4ms
memory: 52224kb
input:
1 10 8 15 18 15 13 4 14 4 17 5
output:
30 37 41 39 34 27 29 26 31 27
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 27ms
memory: 51208kb
input:
1000 4 8 9 7 9 1 9 1 10 2 3 9 3 4 3 2 4 0 4 3 1 4 10 8 4 6 1 9 1 4 4 10 10 1 6 1 9 1 0 2 4 6 4 8 1 6 7 2 5 10 4 9 2 1 4 3 5 5 9 3 9 8 9 4 4 8 5 6 2 10 1 1 7 3 9 2 4 4 2 4 1 2 3 5 2 1 1 4 3 2 0 9 4 7 3 10 1 3 4 1 2 2 6 4 1 2 3 3 1 5 3 5 8 4 2 9 3 4 5 9 10 3 4 6 5 4 0 1 6 4 3 1 10 1 4 1 9 5 7 4 8 1 6 ...
output:
18 18 17 18 9 10 7 10 6 6 5 3 5 5 3 18 16 13 15 9 4 18 17 11 14 9 0 7 8 13 9 11 14 10 12 12 7 6 9 11 11 13 17 16 17 12 14 13 12 10 6 7 12 8 9 5 6 4 4 6 4 4 4 6 5 10 11 11 13 10 5 4 4 8 7 2 5 4 6 11 12 10 10 7 13 17 16 12 9 10 8 6 6 6 7 11 7 9 13 12 11 14 10 12 1...
result:
ok 2420 numbers
Test #4:
score: 0
Accepted
time: 262ms
memory: 50616kb
input:
1000 2 45733740 736448710 1 384264719 4 658671808 379716865 553196572 534986092 1 668964623 4 711670857 237459905 849354895 187613938 2 394629064 371184128 2 616819808 937720703 1 43217931 3 934395080 888433507 810476236 1 587663687 2 542163302 508453558 4 313836277 584869499 445629251 225398284 4 2...
output:
413958095 759315580 384264719 1254322429 1119397578 1175216002 1235849498 668964623 1136546502 1064876265 1239809530 1027491789 580221128 568498660 1085680159 1246130607 43217931 1783849951 1760869165 1721890529 587663687 796390081 779535209 830377481 1020951833 929222211 751348422 70477...
result:
ok 2440 numbers
Test #5:
score: 0
Accepted
time: 1929ms
memory: 179376kb
input:
1 500000 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
ok 500000 numbers
Test #6:
score: 0
Accepted
time: 1919ms
memory: 179444kb
input:
1 499999 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
ok 499999 numbers
Test #7:
score: 0
Accepted
time: 1928ms
memory: 179436kb
input:
1 499800 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
ok 499800 numbers
Test #8:
score: -100
Time Limit Exceeded
input:
1 500000 50831937 44675374 26273308 55922669 39121681 59988372 34492729 33442351 51180456 41692596 39437453 54897084 38001252 46544549 55093280 38264131 54229588 51914925 28566111 46796223 48610138 48548724 51107017 44611895 37985173 46091996 45517937 53008497 48179451 47964156 42155259 47184755 267...