QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#878014 | #9690. Iron Warrior | ucup-team6274# | AC ✓ | 1ms | 3712kb | C++20 | 4.6kb | 2025-02-01 13:03:36 | 2025-02-01 13:03:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
/*--------------------------------------------------------------------------------------*/
#define cin cio
#define cout cio
#define Fs 100000
#define inline __inline__ __attribute__((always_inline))
#define iopt inline IO& operator
#define Tc()(_A==_B&&(_B=(_A=Fi)+fread(Fi,1,100000,stdin),_A==_B)?EOF:*_A++)
#define Pc(Ch)(FS<Fs?Fo[FS++]=Ch:(fwrite(Fo,1,Fs,stdout),Fo[(FS=0)++]=Ch))
int Tp,FS;char Ch,*_A,*_B,Fi[Fs],Fo[Fs],Sk[Fs];
struct IO{
template<typename T>
iopt>>(T&x){x=0;while(!isdigit(Ch=Tc()));while(x=10*x +(Ch&15),isdigit(Ch=Tc()));return*this;}
iopt>>(char*x){int I=0;for(;((x[I]=Tc())!=' ')&&(x[I]!='\n');++I);x[I]='\0';return*this;}
iopt>>(char&x){x=Tc();return*this;}
template<typename T>
iopt<<(T x){if(!x){return Pc('0'),*this;}if(x<0)Pc('-'),x=-x;while(x)Sk[++Tp]=x%10+48,x/=10;while(Tp)Pc(Sk[Tp--]);return*this;}
iopt<<(const char*x){for(;*x!='\0';Pc(*(x++)));return*this;}
iopt<<(char x){Pc(x);return*this;};~IO(){fwrite(Fo,1,FS,stdout),FS=0;}void tie(int){}
}cio;/*----------------------------------------------------------------------------------*/
#define pb push_back
#define pii pair<int,int>
#define piii tuple<int,int,int>
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define fi first
#define se second
#define era erase
#define ins insert
#define it iterator
#define lb lower_bound
#define ub upper_bound
#define exc(exp) if(exp)continue;
#define ret(exp) if(exp)return;
#define stop(exp) if(exp)break;
#define quit(sth) {sth;return;}
#define let(var...) int var;tie(var)
#define siz(vec) ((int)((vec).size()))
#define all(vec) (vec).begin(),(vec).end()
#define unq(vec) sort(all(vec)),(vec).erase(unique(all(vec)),(vec).end())
#define deb(var) cerr<<#var<<'='<<(var)<<"; "
#define debl(var) cerr<<#var<<'='<<(var)<<";\n"
#define int long long
#define db double
#define ld long double
#define ull unsigned long long
#define inf (long long)(1e18)
bool Max(int &x,int y){if(x<y)return x=y,1;return 0;}
bool Min(int &x,int y){if(x>y)return x=y,1;return 0;}
const int mod=998244353;
void Add(int &x,int y){x=x+y<mod?x+y:x+y-mod;}
int add(int x,int y){return x+y<mod?x+y:x+y-mod;}
int fpm(int x,int y){
int ans=1;for(;y;y>>=1,(x*=x)%=mod)if(y&1)(ans*=x)%=mod;return ans;
}
struct num_t{
int l,w[100];
num_t(){
l=0;memset(w,0,sizeof w);
}
num_t(int x){
l=0;memset(w,0,sizeof w);
if(x!=0){
while(x){
w[l++]=x%10;x/=10;
}
--l;
}
}
int& operator [](int k){
return w[k];
}
void out(){
for(int i=l;~i;i--)cout<<w[i];cout<<'\n';
}
friend num_t operator +(num_t a,num_t b){
num_t c;
c.l=max(a.l,b.l);
for(int i=0;i<=c.l;i++){
c[i]+=a[i]+b[i];
c[i+1]+=c[i]/10,c[i]%=10;
}
while(c[c.l+1])++c.l,c[c.l+1]+=c[c.l]/10,c[c.l]%=10;
return c;
}
friend num_t operator *(num_t a,num_t b){
num_t c;
for(int i=0;i<=a.l;i++)
for(int j=0;j<=b.l;j++)
c[i+j]+=a[i]*b[j];
c.l=a.l+b.l;
for(int i=0;i<=c.l;i++){
c[i+1]+=c[i]/10,c[i]%=10;
}
while(c[c.l+1])++c.l,c[c.l+1]+=c[c.l]/10,c[c.l]%=10;
while(c.l>0&&!c[c.l])--c.l;
return c;
}
friend bool operator <=(num_t a,num_t b){
if(a.l<b.l)return 1;
if(a.l>b.l)return 0;
for(int i=a.l;~i;i--){
if(a[i]>b[i])return 0;
if(a[i]<b[i])return 1;
} return 1;
}
};
#define i128 num_t
int n;
i128 C(int m){
if(m==-1)return i128(0);
if(m&1)return i128((m+1)/2)*i128(m);
else return i128(m/2)*i128(m+1);
}
i128 mul(int a,int b){
if(a&1)return i128(a)*i128(b/2);
return i128(a/2)*i128(b);
}
i128 f(int m){
if(m==-1)return i128(0);
if(n&1){
i128 gd=i128(5)+i128(11)*i128(m)+C(m)*i128(5);
i128 co=i128(11)+i128(m+1)*i128(10);
return i128(n+1)*i128(5)+i128((n-1)/2-m)*(i128(11)+i128(m+1)*i128(5)+gd)+co*C((n-1)/2-m-1)+gd+co*i128((n-1)/2-m)+i128(m+1)*i128(5);
}else{
i128 gd=i128(11)+i128(11)*i128(m)+mul(m+3,m)*i128(5);
i128 co=i128(11)+i128(m+2)*i128(10);
return i128(n)*i128(5)+i128(n/2-m-1)*(i128(11)+i128(m+2)*i128(5)+gd)+co*C(n/2-m-2)+gd+i128(n/2-m-1)*co+i128(m+2)*i128(5);
}
}
void work(){
cin>>n;
if(n==0)cout<<"0\n";
else if(n==1)cout<<"20\n";
else if(n==2)cout<<"42\n";
else if(n==3)cout<<"72\n";
else if(n==4)cout<<"105\n";
else{
int l=-1,r=((n&1)?n/2:n/2-1)-1;
while(l<r){
int mid=(l+r+1)>>1;
if(f(mid)<=f(mid+1))l=mid;else r=mid-1;
}
f(l+1).out();
}
}
signed main(){
ios::sync_with_stdio(0),
cin.tie(0),cout.tie(0);
int T=1;while(T--)work();
}
/*
* CONTINUE, NON-STOPPING, FOR THE FAITH
* START TYPING IF YOU DON'T KNOW WHAT TO DO
* STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
1
output:
20
result:
ok answer is '20'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
3
output:
72
result:
ok answer is '72'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
4
output:
105
result:
ok answer is '105'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
5
output:
145
result:
ok answer is '145'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
6
output:
208
result:
ok answer is '208'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
7
output:
248
result:
ok answer is '248'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
8
output:
343
result:
ok answer is '343'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
486036
output:
13810882446441423
result:
ok answer is '13810882446441423'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
857503
output:
75842693981321486
result:
ok answer is '75842693981321486'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
459087
output:
11638561802272893
result:
ok answer is '11638561802272893'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
326354
output:
4181111331905669
result:
ok answer is '4181111331905669'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
755041
output:
51774938180590304
result:
ok answer is '51774938180590304'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
1000000
output:
120283726342420340
result:
ok answer is '120283726342420340'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
562451495
output:
21401951468280078633294014
result:
ok answer is '21401951468280078633294014'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
100214615
output:
121057415160393160185480
result:
ok answer is '121057415160393160185480'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
726997959
output:
46216571009844858875968944
result:
ok answer is '46216571009844858875968944'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
883477562
output:
82943950684199531529718356
result:
ok answer is '82943950684199531529718356'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
456878752
output:
11470993586298146794567272
result:
ok answer is '11470993586298146794567272'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1000000000
output:
120281308501417045326995605
result:
ok answer is '120281308501417045326995605'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
151798318021627311
output:
420725672820572820226091469784149314525410684999074
result:
ok answer is '420725672820572820226091469784149314525410684999074'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
466154514052238226
output:
12183941850211915347991952173009567537536253846445099
result:
ok answer is '12183941850211915347991952173009567537536253846445099'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
262261097390039057
output:
2169700342816432479937347535029836266637820523889883
result:
ok answer is '2169700342816432479937347535029836266637820523889883'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
409768988622482114
output:
8275903133852517858111731626726122320253985666412809
result:
ok answer is '8275903133852517858111731626726122320253985666412809'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
361773749401383499
output:
5695204039674250675619463634360070429230287130689713
result:
ok answer is '5695204039674250675619463634360070429230287130689713'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1000000000000000000
output:
120281306081172036692984324273260313737335405903162447
result:
ok answer is '120281306081172036692984324273260313737335405903162447'
Extra Test:
score: 0
Extra Test Passed