QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#878014#9690. Iron Warriorucup-team6274#AC ✓1ms3712kbC++204.6kb2025-02-01 13:03:362025-02-01 13:03:36

Judging History

This is the latest submission verdict.

  • [2025-02-01 13:03:36]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3712kb
  • [2025-02-01 13:03:36]
  • Submitted

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