QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75601#4917. 中奖率4182_543_731Compile Error//C++203.2kb2023-02-05 21:31:442023-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]
  • 评测
  • [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();
      |                 ~~~~~^~~~~~~~~