QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21312#2822. 不等式glory_to_the_qy#WA 4ms36904kbC++203.0kb2022-03-04 15:07:262022-05-08 02:52:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 02:52:10]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:36904kb
  • [2022-03-04 15:07:26]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
#define int ll
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO
{
    #define BUF_SIZE 100000
    bool IOerror=0;
    inline char nc()
	{
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline ll read()
	{
        bool sign=0; char ch=nc();ll x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return 0;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
        return x;
    }
    #undef BUF_SIZE
};
using namespace fastIO;
int a[2000020],b[2000020];
struct node
{
	int x,y;
	// long double x;
	int id;
}p[2000020];
bool cmp(node p1,node p2)
{
	return p1.x*p2.y<p2.x*p1.y;
	// return p1.x<p2.x;
}
struct line
{
	int k=0,b=0;
	line(){}
	line(int kk,int bb){k=kk,b=bb;}
}c[2000020];
line operator + (line a,line b){return line(a.k+b.k,a.b+b.b);}
int c2[2000020],pos[2000020];
void add(int nl,int nr,int l,int r,int k,int b,int x)
{
	if(l<=nl&&nr<=r)
	{
		c[x].k+=k;
		c[x].b+=b;
		return;
	}
	int mid=(nl+nr)/2;
	if(l<=mid)add(nl,mid,l,r,k,b,x<<1);
	if(r>mid)add(mid+1,nr,l,r,k,b,x<<1|1);
}
void add2(int l,int r,int p,int v,int x)
{
	c2[x]+=v;
	if(l==r)return;
	int mid=(l+r)/2;
	if(p<=mid)add2(l,mid,p,v,x<<1);
	else add2(mid+1,r,p,v,x<<1|1);
}
line query(int l,int r,int p,int x)
{
	line ans=c[x];
	if(l==r)return ans;
	int mid=(l+r)/2;
	if(p<=mid)ans=ans+query(l,mid,p,x<<1);
	else ans=ans+query(mid+1,r,p,x<<1|1);
	return ans;
}
int find(int l,int r,int v,int x)
{
	if(l==r)return l;
	int mid=(l+r)/2;
	if(c2[x<<1]<v)return find(mid+1,r,v-c2[x<<1],x<<1|1);
	else return find(l,mid,v,x<<1);
}
signed main()
{
//	freopen("i.in","r",stdin);
//	freopen("i.out","w",stdout);
	int n=qr;
	for(int i=1;i<=n;i++)
	{
		in(a[i]),in(b[i]);
		if(a[i]<0)a[i]*=-1,b[i]*=-1;
		if(a[i]!=0)p[i]=(node){-b[i],a[i],i};
		else p[i]=(node){0,1,i};
	}
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		pos[p[i].id]=i;
	}
	int sum=0,ad=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0)ad+=abs(b[i]);
		else
		{
			sum+=a[i];
			add(1,n+1,1,pos[i],-a[i],-b[i],1);
			add(1,n+1,pos[i]+1,n+1,a[i],b[i],1);
			add2(1,n+1,pos[i],a[i],1);
		}
		int pp=find(1,n+1,(sum+1)/2,1);
		line now=query(1,n+1,pp,1);
		printf("%.8f\n",abs(now.k*(1.0*p[pp].x/p[pp].y)+now.b+ad));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 36904kb

input:

1000
61238 60248 73732 -26564 -93007 4478 -39783 -29386 6714 -96099 58853 29344 88517 -7643 -16343 97123 82004 96690 -63916 13672 -72104 -93128 -33526 4108 -5475 -53323 57787 15891 -9523 -10161 -96799 -83119 77140 97223 -56595 -95821 24758 73652 58307 -22694 -62422 2448 59087 -47128 67302 -53844 -61...

output:

0.00000000
82310.68963272
86210.45246057
117511.88112723
213287.62274883
245465.21305923
248846.39270162
345182.52769146
445820.76720032
456415.40906598
553014.99412947
555508.82070167
609095.42505403
627287.53595099
634829.78098880
691329.76790628
751826.75251899
817445.25945756
872809.58411884
932...

result:

wrong answer 2nd numbers differ - expected: '21040.3674840', found: '82310.6896327', error = '2.9120367'