QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #846690 | #9920. Money Game 2 | Zawos | RE | 0ms | 0kb | C++23 | 6.3kb | 2025-01-07 12:26:38 | 2025-01-07 12:26:39 |
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);
freopen("01.01.2025\\input.txt","r",stdin);
freopen("01.01.2025\\output.txt","w",stdout);
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;
}
vector<ll> a(2*n);
FOR(i,0,n) a[i] = v[i],a[i+n] = v[i];
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;
actual[k] -= actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}else{
actual[k-1] += actual[k]>>1;
actual[k] -= 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;
actual[k] -= actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}else{
actual[k-1] += actual[k]>>1;
actual[k] -= 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);
for(int i = n; i < 2*n; i++){
int p1 = i;
while(p1 >i-n){
if(a[p1] > 1){
a[p1-1] += a[p1]/2;
a[p1] -= a[p1]/2;
p1--;
}else break;
}
if(i-p1 > 35){
for(int j = p1; j != i; j= (j+1)){
if(i-j > 35) 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){
if(a[p1] > 1){
a[p1+1] += a[p1]/2;
a[p1] -= a[p1]/2;
p1++;
}else break;
}
if(p1-i > 35){
for(int j = p1; j != i; j= j-1){
if(j-i > 35) 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;
actual[k] -= actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}else{
actual[k-1] += actual[k]>>1;
actual[k] -= 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;
actual[k] -= actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}else{
actual[k-1] += actual[k]>>1;
actual[k] -= actual[k]>>1;
if(actual[k]&1){
actual[k] = 1;
}else actual[k] = 0;
}
}
}
ll ans = 0;
if(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: 0
Dangerous Syscalls
input:
3 5 2 1 4 3 5 5 2 1 3 1 2 1 1000000000