QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #846793 | #9920. Money Game 2 | Zawos | WA | 627ms | 18624kb | C++23 | 6.3kb | 2025-01-07 14:25:26 | 2025-01-07 14:25:31 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<ll> v(n);
FOR(i,0,n) cin >> v[i];
if(n == 1){
cout <<v[0]<<'\n';
continue;
}else if(n == 2){
cout <<v[0] +v[1]/2<<" "<<v[1] +v[0]/2<<'\n';
continue;
}
if(n <=70){
for(int i = 0; i < n; i++){
vector<ll> extra(n-2);
vector<ll> extra2(n-2);
vector<ll> actual(n-2);
for(int j = 0; j < n-2; j++) actual[j] =v[(i+j+1)%n];
for(int j = 0; j < n-2; j++){
if(j > 0) extra[j] = extra[j-1];
for(int k = j; k >= 0; k--){
if(k == 0){
extra[j] += actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else{
actual[k] = 0;
}
}else{
actual[k-1] += actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}
}
}
for(int j = 0; j < n-2; j++) actual[j] = v[(i-j-1+n)%n];
for(int j = 0; j < n-2; j++){
if(j > 0) extra2[j] = extra2[j-1];
for(int k = j; k >= 0; k--){
if(k == 0){
extra2[j] += actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}else{
actual[k-1] += actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}
}
}
ll ans = v[i];
for(int j = 0; j < n-2; j++){
ans = max(ans,v[i]+extra[j]+extra2[n-j-3]);
}
cout <<ans<<" ";
}
cout<<'\n';
continue;
}
vector<int> ev(n,-1);
vector<int> rev(n,-1);
vector<ll> a(2*n);
FOR(i,0,n) a[i] = v[i],a[i+n] = v[i];
for(int i = n; i < 2*n; i++){
int p1 = i;
while(p1 >i-n+1){
if(a[p1] > 1){
a[p1-1] += a[p1]>>1;
if(a[p1]&1){
a[p1] = 1;
}else a[p1] = 0;
p1--;
}else break;
}
if(i-p1 > 35){
for(int j = p1; j != i; j++){
if(i-j > 35){
// assert(ev[j%n] == -1);
ev[j%n] = i-j;
}
}
}
}
FOR(i,0,n) a[i] = v[i],a[i+n] = v[i];
for(int i = n-1; i >= 0; i--){
int p1 = i;
while(p1 < i+n-1){
if(a[p1] > 1){
a[p1+1] += a[p1]>>1;
if(a[p1]&1){
a[p1] = 1;
}else a[p1] = 0;
p1++;
}else break;
}
if(p1-i > 35){
for(int j = p1; j != i; j--){
if(j-i > 35){
// assert(rev[j%n] == -1);
rev[j%n] = j-i;
}
}
}
}
for(int i = 0; i < n; i++){
vector<ll> extra(35);
vector<ll> extra2(35);
vector<ll> actual(35);
for(int j = 0; j < 35; j++) actual[j] =v[(i+j+1)%n];
for(int j = 0; j < 35; j++){
if(j > 0) extra[j] = extra[j-1];
for(int k = j; k >= 0; k--){
if(k == 0){
extra[j] += actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}else{
actual[k-1] += actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}
}
}
for(int j = 0; j < 35; j++) actual[j] = v[(i-j-1+n)%n];
for(int j = 0; j < 35; j++){
if(j > 0) extra2[j] = extra2[j-1];
for(int k = j; k >= 0; k--){
if(k == 0){
extra2[j] += actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}else{
actual[k-1] += actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}
}
}
ll ans = v[i];
if(rev[i] !=-1 &&ev[i] != -1&&rev[i] +ev[i] <=n-1) ans = max(ans,v[i]+extra.back()+extra2.back()+2);
for(int j = 0; j <35; j++){
if(rev[i] != -1&& j+1+rev[i] <= n-1){
ans = max(ans,v[i]+extra[j]+extra2.back()+1);
}else ans = max(ans,v[i]+extra[j]+extra2.back());
}
for(int j = 0; j <35; j++){
if(ev[i] != -1&& j+1+ev[i] <= n-1){
ans = max(ans,v[i]+extra2[j]+extra.back()+1);
}else ans = max(ans,v[i]+extra2[j]+extra.back());
}
cout <<ans<<" ";
}
cout <<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
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: 0ms
memory: 3832kb
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: 1ms
memory: 3616kb
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 16 18 15 18 19 ...
result:
ok 2420 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 3604kb
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 704770986 755...
result:
ok 2440 numbers
Test #5:
score: -100
Wrong Answer
time: 627ms
memory: 18624kb
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 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 ...
result:
wrong answer 36th numbers differ - expected: '3', found: '4'