QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75601 | #4917. 中奖率 | 4182_543_731 | Compile Error | / | / | C++20 | 3.2kb | 2023-02-05 21:31:44 | 2023-02-05 21:31:47 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-02-05 21:31:47]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-02-05 21:31:44]
- 提交
answer
#pragma GCC optimize(3)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
//simple integer
#define ll long long
ll bs=1e18;
struct integer{
vector<ll> v;
explicit operator bool()const{return !v.empty();}
void add(ll a)
{
ll rs=a;
for(int i=0;rs;i++)
{
if(i>=v.size())v.push_back(0);
rs+=v[i];
v[i]=rs%bs;
rs/=bs;
}
}
void mul(ll a)
{
__int128 rs=0;
for(int i=0;i<v.size()||rs;i++)
{
if(i>=v.size())v.push_back(0);
rs+=(__int128)a*v[i];
v[i]=rs%bs;
rs/=bs;
}
}
void div(ll a)
{
int sz=v.size();
ll rs=0;
for(int i=sz-1;i>=0;i--)
{
__int128 ri=(__int128)bs*rs+v[i];
v[i]=ri/a;rs=ri%a;
}
while(v.size()&&v.back()==0)v.pop_back();
}
ll mod(ll a)
{
int sz=v.size();
ll rs=0;
for(int i=sz-1;i>=0;i--)
{
__int128 ri=(__int128)bs*rs+v[i];
rs=ri%a;
}
return rs;
}
};
#define N 105000
char s[N];
integer input()
{
integer si;
scanf("%s",s+1);
ll s1=1,s2=0;
int le=1;
while(s[le+1])le++;
while(le)
{
s2+=s1*(s[le]-'0');s1*=10;
if(s1==bs)si.v.push_back(s2),s1=1,s2=0;
le--;
}
if(s2)si.v.push_back(s2);
return si;
}
void output(integer s)
{
if(!s){printf("0\n");return;}
printf("%lld",s.v.back());
for(int i=(int)s.v.size()-2;i>=0;i--)printf("%018lld",s.v[i]);
printf("\n");
}
int n,q,a,su[N],fg;
ll la[N];
ll calc(ll a,ll b)
{
ll si=0;
//sum la*s/lx/n-i/n
for(int i=1;i<=n;i++)if(la[i]>0)
{
__int128 ri=(__int128)la[i]*a+b*n-i*b;
si+=ri/n/b;
}
return si;
}
void query1(integer s)
{
if(!fg)
{
int ci=0;
for(int i=1;i<=n;i++)if(la[i]==0)ci++;
int ri=s.mod(ci);
s.div(ci);s.mul(n);
for(int i=1;i<=n;i++)if(la[i]==0)
{
ri--;
if(!ri)s.add(i);
}
output(s);
return;
}
ll s1=0;
for(int i=1;i<=n;i++)if(la[i]>0)s1+=la[i];
ll re=s.mod(s1);s.div(s1);
if(s)s.add(-1),re+=s1;
ll lb=0,rb=2ll*n*n*n,fr=1ll*n*n,as=0;
while(lb<=rb)
{
ll mid=(lb+rb)>>1;
if(calc(mid,fr)<re)as=mid,lb=mid+1;
else rb=mid-1;
}
re-=calc(as,fr);
vector<pair<ll,int> > tp;
for(int i=1;i<=n;i++)if(la[i]>0)
{
__int128 ri=(__int128)la[i]*as+fr*n-i*fr;
if(ri/n/fr!=(ri+la)/n/fr)tp.push_back(make_pair(la[i],i));
}
sort(tp.begin(),tp.end());
int sx=tp[re-1].second;
ll ry=(__int128)(as+1)*la[sx]/fr;
s.mul(la[sx]);s.mul(n);s.add(ry);
output(s);
}
void query2(integer s)
{
int id=s.mod(n);
if(!id)id=n;
if(la[id]<0||(la[id]==0&&fg)){printf("inf\n");return;}
if(la[id]==0)
{
s.div(n);
int ci=0,c2=0;
for(int i=1;i<=n;i++)if(la[i]==0)ci++,c2+=id<n&&i<=id;
s.mul(ci);s.add(c2);
output(s);
return;
}
ll lx=la[id],rs=lx*n,ri=s.mod(rs);
s.div(rs);
if(s)s.add(-1),ri+=rs;
ll s1=0;
for(int i=1;i<=n;i++)if(la[i]>0)s1+=la[i];
s.mul(s1);
//sum la*s/lx/n-i/n
for(int i=1;i<=n;i++)if(la[i]>0)
{
__int128 r1=(__int128)la[i]*ri-i*lx-(la>lx)+n*lx;
s.add(r1/n/lx);
}
output(s);
}
int main()
{
scanf("%d%d%s",&n,&q,s+1);
for(int i=1;i<=n;i++)su[i]=su[i-1]+s[i]-'0',la[i]=1ll*su[i]*n-1ll*su[n]*i;
for(int i=1;i<n;i++)if(la[i]>0)fg=1;
while(q--)
{
scanf("%d",&a);integer b=input();
if(a==1)query1(b);else query2(b);
}
}
詳細信息
answer.code: In function ‘void query1(integer)’: answer.code:127:36: error: invalid operands of types ‘long long int*’ and ‘int’ to binary ‘operator/’ 127 | if(ri/n/fr!=(ri+la)/n/fr)tp.push_back(make_pair(la[i],i)); | ~~~~~~~^~ | | | | | int | long long int* answer.code: In function ‘void query2(integer)’: answer.code:158:56: error: ISO C++ forbids comparison between pointer and integer [-fpermissive] 158 | __int128 r1=(__int128)la[i]*ri-i*lx-(la>lx)+n*lx; | ~~^~~ answer.code: In function ‘integer input()’: answer.code:62:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 62 | scanf("%s",s+1); | ~~~~~^~~~~~~~~~ answer.code: In function ‘int main()’: answer.code:165:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 165 | scanf("%d%d%s",&n,&q,s+1); | ~~~~~^~~~~~~~~~~~~~~~~~~~ answer.code:170:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 170 | scanf("%d",&a);integer b=input(); | ~~~~~^~~~~~~~~