QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589378#6812. Draw a triangleSunlight9#WA 30ms3852kbC++201.5kb2024-09-25 17:35:382024-09-25 17:35:39

Judging History

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

  • [2024-09-25 17:35:39]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:3852kb
  • [2024-09-25 17:35:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll =__int128;
//using ll = long long;
int t;
ll x,y,a,b,c;
void ex_gcd(long long int al,long long int bl)
{
	if(bl==0LL)
	{
		x=1LL;y=0LL;return;
	}
	else
	{
		ex_gcd(bl,al%bl);
		long long tmp=x;
		x=y;y=tmp-y*(al/bl);
	}
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    long long x1,x2,y1,y2,x3,y3;
    cin>>t;
    while(t--)
    {
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2)
        {
            cout<<x1+1LL<<" 1\n";
            continue;
        }
        if(y1==y2)
        {
            cout<<"1 "<<y1+1LL<<'\n';
            continue;
        }
        a=y1-y2;b=x2-x1;
        c=x2*y1-x1*y2;
        ll aa=a,bb=b;
        if(aa<0) aa=-aa;
        if(bb<0) bb=-bb;

        ll gcdk=__gcd(aa,bb);

        a/=gcdk;b/=gcdk;
        ll num_l=c/gcdk;
        if(c%gcdk==0LL) num_l--;
        ll num_r=c/gcdk;
        if(c%gcdk==0LL) num_r++;

        ll sum1=c-num_l*gcdk;
        ll sum2=num_r*gcdk-c;
        ll num;
        if(sum1<=sum2) num=num_l;
        else num=num_r;

//        cerr<<a<<" "<<b<<" "<<c<<"  asd"<<endl;
        ex_gcd(a,b);
//         cerr<<x<<" "<<y<<" "<<c<<"  asd"<<endl;
        x*=num;y*=num;
//        if(x>1e18)
//        {
//
//        }
        assert(x <= 1E18 and y <= 1E18);
        assert(x >= -1E18 and y >= -1E18);
        
        cout<<format("{}", x) <<" "<< format("{}", y) <<'\n';
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3708kb

input:

3
1 0 1 4
0 1 0 9
0 0 2 2

output:

2 1
1 1
0 -1

result:

ok T=3 (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 30ms
memory: 3852kb

input:

50000
66620473 -33485015 66620223 -33485265
43307886 98029243 43307636 98028994
-88895230 -3180782 -88895480 -3181030
-90319745 20018595 -90319995 20018348
-56783257 84789686 -56783507 84789440
-81798038 90629147 -81798288 90628902
98942945 -939146 98942695 -939390
-42532151 -57203475 -42532401 -572...

output:

0 100105487
-13723647137 -13723647137
-10625410771 -10625410771
-2267030938578 -2239717312812
-1090149184444 -1072566133082
-8539561213 -8539561213
511914166638 499725734099
424314497992 412417829824
319508495801 309201770130
-578593659057 -557743437109
-735414464 -735414464
475560039227 45465630123...

result:

wrong answer wa on query #1 (test case 1)