QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #414931 | #2929. Concert Rehearsal | TheSleepyDevil | WA | 2ms | 15416kb | C++17 | 6.5kb | 2024-05-20 03:21:46 | 2024-05-20 03:21:48 |
Judging History
answer
/*
Hell, 'til I reach Hell, I ain't scared
Mama checkin' in my bedroom, I ain't there
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Major ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TxtIO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define read(a,n) for(int i = 0 ; i<n ; i++) cin>>a[i];
#define write(a) for(auto x : a) cout<<x<<" ";
#define int long long
#define pb push_back
#define all(a) a.begin(),a.end()
#define el "\n"
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf=4e18;
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,1,0,-1,1,-1,1,-1};
const int mod=1e9+7;
const int MAX =1e6+7;
// ---------------------------Function----------------------------------//
int n,p,k;
vector<array<int,2>>arr;
vector<int>pre;
int check(int st,int kam){
int sum=0;
int cnt=kam/n,lft=kam%n;
sum+=cnt*pre[n-1];
if((st+lft-1<=0))return sum;
sum+=pre[min(n-1,st+lft-1)]-(!st?0:pre[st-1]);
int mnfo2=0;
if((st+lft-1)>=n){
mnfo2=n-(st+lft-1);
sum+=pre[mnfo2];
}
// cout<<sum<<" "<<mnfo2<<el;
// cout<<mnfo2<<el;
return sum;
}
int vis[MAX],ans[MAX],base[MAX];
void TestCake(){
cin>>n>>p>>k;
int sum=0;
for(int i=0;i<n;i++){
int x;cin>>x;
arr.pb({x,i});sum+=x;
pre.pb(sum);
}
vector<array<int,2>>nxt;
for(int i=0;i<n;i++){
int l=1,r=1e9,z=1;
while(l<=r){
int mid=(l+r)/2;
if(check(i,mid)>p){
z=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
// cout<<check(i,r)<<" "<<i<<" "<<r<<el;
nxt.pb({(i+r)%n,r});
// cout<<i<<" "<<(i+r)%n<<" "<<r<<el;
}
memset(vis,-1,sizeof vis);
int st=0,cnt=0;
vector<array<int,3>>here;
while(vis[st]==-1){
vis[st]=cnt;
here.pb({st,nxt[st][0],nxt[st][1]});
st=nxt[st][0];
cnt++;
}
here.pb({st,nxt[st][0],nxt[st][1]});
// cout<<cnt<<el;
// for(auto x : here){
// cout<<x[0]<<" "<<x[1]<<" "<<x[2]<<el;
// }
if(cnt>=k){
for(int i=0;i<here.size()-1&&k--;i++){
int l=here[i][0],r=here[i][1];
// cout<<l<<" "<<r<<el;
int m3aya=here[i][2]/n,zyada=here[i][2]%n;
ans[0]+=m3aya;
ans[n]-=m3aya;
r=(l+zyada-1);
r+=n;r%=n;
ans[l]++;
if(r>=l){
ans[r+1]--;
}
else{
ans[n]--;
ans[0]++;
ans[r+1]--;
}
}
}
else{
k-=cnt;
// cout<<k<<" "<<cnt<<el;
int id=0;
for(int i=0;i<here.size();i++){
if(here[i]==here.back()){id=i;break;}
}
for(int i=id;i<here.size()-1;i++){
int l=here[i][0],r=here[i][1];
// cout<<l<<" "<<r<<el;
int m3aya=(here[i][2]/n),zyada=(here[i][2]%n);
ans[0]+=m3aya;
ans[n]-=m3aya;
if(!zyada)continue;
r=(l+zyada-1);
r+=n;r%=n;
// cout<<m3aya<<" "<<zyada<<" "<<l<<" "<<r<<el;
ans[l]++;
if(r>=l){
ans[r+1]--;
}
else{
ans[n]--;
ans[0]++;
ans[r+1]--;
}
//
}
for(int z=1;z<n;z++)ans[z]+=ans[z-1];
int sz=(cnt-id);
int have=(k/sz),bzboz=(k%sz);
for(int i=0;i<n;i++){
// cout<<ans[i]<<" "<<have<<el;
ans[i]+=(ans[i]*(have));
}
//base
for(int i=0;i<id;i++){
int l=here[i][0],r=here[i][1];
// cout<<l<<" "<<r<<el;
int m3aya=here[i][2]/n,zyada=here[i][2]%n;
base[0]+=m3aya;
base[n]-=m3aya;
r=(l+zyada-1);
r+=n;r%=n;
base[l]++;
if(r>=l){
ans[r+1]--;
}
else{
base[n]--;
base[0]++;
base[r+1]--;
}
}
//
for(int i=id;i<here.size()-1&&bzboz--;i++){
int l=here[i][0],r=here[i][1];
// cout<<l<<" "<<r<<el;
int m3aya=here[i][2]/n,zyada=here[i][2]%n;
base[0]+=m3aya;
base[n]-=m3aya;
r=(l+zyada-1);
r+=n;r%=n;
base[l]++;
if(r>=l){
base[r+1]--;
}
else{
base[n]--;
base[0]++;
base[r+1]--;
}
}
int mn=inf;
for(int i=1;i<n;i++)base[i]+=base[i-1];
for(int i=0;i<n;i++){
ans[i]+=base[i];
mn=min(mn,ans[i]);
}
cout<<mn<<el;return;
}
int mn=ans[0];
// cout<<ans[0]<<" ";
for(int z=1;z<n;z++){
ans[z]+=ans[z-1];
// cout<<ans[z]<<" ";
mn=min(mn,ans[z]);
}
cout<<mn<<el;
}
//------------------------------Main---------------------------//
signed main(){
Major
int T = 1;
// cin >> T;
while(T--){
TestCake();
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 14924kb
input:
3 20 10 6 9 5
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 2ms
memory: 12744kb
input:
5 11 2 5 5 5 5 5
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 12604kb
input:
7 11 3 1 2 3 4 5 6 7
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 15324kb
input:
4 8 9 2 7 2 3
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 2ms
memory: 15292kb
input:
1 3 7 2
output:
7
result:
ok single line: '7'
Test #6:
score: 0
Accepted
time: 0ms
memory: 15416kb
input:
1 1000000000 1000000000 1
output:
1000000000000000000
result:
ok single line: '1000000000000000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 13852kb
input:
5 999999999 999999999 2 1 4 7 3
output:
58823528941176471
result:
ok single line: '58823528941176471'
Test #8:
score: 0
Accepted
time: 2ms
memory: 13744kb
input:
5 5 1000 2 2 2 2 2
output:
400
result:
ok single line: '400'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 13792kb
input:
980 991 978 2 1 2 1 2 3 1 1 1 3 3 3 2 2 2 2 3 3 1 3 1 2 2 3 1 2 3 3 2 3 1 2 2 3 1 3 1 3 2 2 2 1 1 2 3 3 1 2 1 1 1 2 2 2 3 3 2 1 3 3 1 3 3 1 1 2 1 1 1 1 2 1 2 3 2 1 1 3 3 2 2 1 3 3 3 2 2 3 1 2 3 3 2 2 3 2 3 2 2 2 1 3 3 1 1 3 1 2 2 2 2 1 2 2 1 1 3 2 1 1 3 1 2 3 3 3 3 3 2 2 2 3 3 1 1 2 1 3 3 3 2 2 2 3 ...
output:
489
result:
wrong answer 1st lines differ - expected: '492', found: '489'