QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404261#6812. Draw a trianglejiajieshiWA 21ms3612kbC++209.2kb2024-05-03 17:20:282024-05-03 17:20:28

Judging History

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

  • [2024-05-03 17:20:28]
  • 评测
  • 测评结果:WA
  • 用时:21ms
  • 内存:3612kb
  • [2024-05-03 17:20:28]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long 
#define pii pair<int,int>
#define pss pair<string,string>
#define fi first
#define se second
#define pb push_back
#define pbb pair<bool,bool>
#define un unsigned
#define ull unsigned long long
#define	int_INF 0x3f3f3f3f
#define LL long long
#define ll_INF 0x3f3f3f3f3f3f3f3f
#define lb long double
#define db double
#define re return
#define pll pair<ll,ll>
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define cer(a) cerr<<#a<<'='<<(a)<<"@ line"<<__LINE__<<endl
#define cer2(a,b) cerr<<#a<<'='<<(a)<<','<<#b<<'='<<(b)<<"@ line"<<__LINE__<<endl
#define cer3(a,b,c) cerr<<#a<<'='<<(a)<<','<<#b<<'='<<(b)<<','<<#c<<'='<<(c)<<','<<"@ line"<<__LINE__<<endl
#define pdd pair<db,db>
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define KV(x) #x << " = " << x << ";"
#define DEBUG DebugLine(__LINE__)
#define bitCount(x) __builtin_popcount(x)
using namespace std;
const int maxn=2e5+100;
const ll mode=998244353;
const ll mode2=1e9+7;
const ll inf=9223372036854775807;
const db eps=1e-6;
typedef pair<int,int> hashv;
mt19937 mrand(random_device{}()); 
hashv operator + (hashv a,hashv b) {
	int c1=a.fi+b.fi,c2=a.se+b.se;
	if (c1>=mode) c1-=mode;
	if (c2>=mode2) c2-=mode2;
	return mp(c1,c2);
}

hashv operator - (hashv a,hashv b) {
	int c1=a.fi-b.fi,c2=a.se-b.se;
	if (c1<0) c1+=mode;
	if (c2<0) c2+=mode2;
	return mp(c1,c2);
}

hashv operator * (hashv a,hashv b) {
	return mp(1ll*a.fi*b.fi%mode,1ll*a.se*b.se%mode2);
}
int rnd(int x) { return mrand() % x;}
struct DebugLine {
  explicit DebugLine(int lineno) { std::cerr << lineno << "L "; }
 
  ~DebugLine() { std::cerr << std::endl; }
 
  template <typename T> DebugLine &operator<<(T &&v) {
    std::cerr << std::forward<T>(v);
    return *this;
  }
};
double PI = 3.141592653;
double my_cos(double x){
    return cos(x*PI / 180.0);
}
double my_sin(double x){
    return sin(x*PI / 180.0);
}
double my_tan(double x){
    return tan(x*PI / 180.0);
}
ll n,m,a[maxn];
ll sum,ans;
string str;
vector<int>vt;
int vis[maxn]; 
ll ksm(ll a,ll b,ll p)
{
	ll res=1ll;
	while(b)
	{
		if(b&1)
		res=res*a%p;
		b>>=1;
		a=a*a%p;
	}
	return res;
}
struct Hash_char{
    const ll mod=998244353, base=131;
    ll p[maxn], g[maxn];
    void getp(){
        p[0]=1;
        for(int i=1; i<maxn; i++){
            p[i]=p[i-1]*base%mod;
        }
    }
    LL Hash(char s[]){
        int len=strlen(s+1);
        g[0]=0, g[1]=s[1];
        for(int i=2; i<=len; i++){
            g[i]=(g[i-1]*base+s[i])%mod;
        }
        return g[len];
    }
    LL getLR(int l, int r){//µÃµ½s[l]-s[r]µÄhashÖµ 
        if(l>r) return 0;
        LL ans=((g[r]-g[l-1]*p[r-l+1])%mod+mod)%mod;
        return ans;
    }
    
 
}T[2];
LL strfz(int pos, int l, int r){//pos:Õý·´´®,·­×ªl, r¡£ 
    LL ans=T[pos].getLR(1, l-1)*T[pos].p[n-l+1]%T[pos].mod;
    LL res=T[pos^1].getLR(n-r+1, n-r+1+r-l)*T[pos].p[n-r]%T[pos].mod;
    ans=ans+res+T[pos].getLR(r+1, n);
    return ans%T[pos].mod;
}

template<const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {} 
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    bool operator == (const ModInt &a) const { return x == a.x; };
    bool operator != (const ModInt &a) const { return x != a.x; };
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
    friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
    friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}
 
    ModInt pow(int64_t n) const {
        if(n == 0) return 1;
        ModInt res(1), mul(x);
        while(n){
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
     
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if (u < 0) u += mod;
        return u;
    }
     
};
using mint = ModInt<1000000007>;
ll ecgcd(ll a,ll b,ll& x,ll& y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    ll d=ecgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
//class manacherWrapper
//{
//    private:
//        int l_;
//        string s_;
//    public:
//        std::vector<int> p;
//        std::vector<int> b;
//        std::vector<int> s;
//        explicit manacherWrapper(string str)
//        {
//            auto l = str.size();
//            //rebuild
//            l_ = l;
//            s_.resize(((l_ + 1) << 1) | 1);
//            p.resize(((l_ + 1) << 1) | 1);
//            b.resize(l_);
//            s.resize(l_ + 1);
// 
//            s_[0] = '$', s_[1] = '#';
// 
//            for (int i = 0; i < l_; ++i)
//                s_[(i + 1) << 1] = str[i], s_[((i + 1) << 1) | 1] = '#';
//            l_ = (l_ + 1) << 1;
//            //calc p
//            int mx = 0, id;
//            for (int i = 0; i < l_; ++i)
//            {
//                if (mx > i)p[i] = std::min(p[(id << 1) - i], mx - i);
//                else p[i] = 1;
//                for (; s_[i - p[i]] == s_[i + p[i]]; p[i]++);
//                if (p[i] + i > mx)
//                {
//                    mx = p[i] + i;
//                    id = i;
//                }
//            }
//            //calc b and s
//            for (int i = 0; i < l; ++i)
//            {
//                auto lp = get(i);
//                b[i - (lp >> 1)] = std::max(b[i - (lp >> 1)], lp);
//                s[i - (lp >> 1)]++, s[i + 1]--;
//                if (i + 1 >= l)break;
//                lp = get(i, i + 1);
//                if (lp > 0)
//                {
//                    b[i + 1 - (lp >> 1)] = std::max(b[i + 1 - (lp >> 1)], lp);
//                    s[i + 1 - (lp >> 1)]++, s[i + 1]--;
//                }
//            }
//            for (int i = 1; i < l; ++i)
//            {
//                b[i] = std::max(b[i], b[i - 1] - 2);
//                s[i] += s[i - 1];
//            }
//        }
// 
//        int get(int pos)
//        {
//            return (int) p[(pos + 1) << 1] - 1;
//        }
// 
//        int get(int posl, int posr)
//        {
//            return (int) p[((posl + 1) << 1) | 1] - 1;
//        }
// 
//        int longestBegin(int begin)
//        {
//            return b[begin];
//        }
// 
//        int totalBegin(int begin)
//        {
//            return s[begin];
//        }
// 
//        bool isPalindrome(int l,int r)
//        {
//            if (l > r)std::swap(l, r);
//            auto mid = (l + r) >> 1;
//            auto len = (r - l + 1);
//            return len & 1 ? get(mid) >= len : get(mid, mid + 1) >= len;
//        }
//};
//void scan(__int128 &x){//input
//	x = 0;
//	int f = 1;
//	char ch;
//	if((ch = getchar()) == '-'){
//		f = -1;
//	}else{
//		x = x * 10 + (ch - '0');
//	}
//	while((ch = getchar()) >= '0' && ch <= '9'){
//		x = x * 10 + (ch - '0');
//	}
//	x *= f;
//}
//void print(__int128 x){//output 
//	if(x < 0){
//		x = -x;
//		putchar('-');
//	}
//	if(x > 9){
//		print(x/10);//recursion
//	}
//	putchar(x%10+'0');
//}
ll X[3],Y[3];
ll Gcd(ll x,ll y)
{
	if(y==0)
	return x;
	return Gcd(y,x%y);
}
void solve()
{
	cin>>X[1]>>Y[1]>>X[2]>>Y[2];
	if(X[1]==X[2])
	{
		cout<<X[1]-1<<" "<<0;
		cout<<'\n';
		return;
	}
	if(Y[1]==Y[2])
	{
		cout<<Y[1]+1<<" "<<0<<'\n';
		return;
	}
	ll k_up=Y[2]-Y[1];
	ll k_down=X[2]-X[1];
	ll gcd=Gcd(k_up,k_down);
	k_up/=gcd;
	k_down/=gcd;
//	Y[1]=k*X[1]+b
    ll b_down=k_down;
    ll b_up=Y[1]*k_down-k_up*X[1];
    gcd=__gcd(b_up,b_down);
	b_down/=gcd;
	b_up/=gcd;
	ll ansx=k_down;
	ll ansy;
	if(b_down==1)
	{
		ansy=k_up+b_up+1;
	}else ansy=k_up+1;
	cout<<ansx<<" "<<ansy<<'\n';
	
	
}
int main(){
	#ifndef ONLINE_JUDGE
		freopen("C:\\Users\\JIAJIEASHI\\Desktop\\in.cpp","r",stdin);
	//	freopen("out.cpp","w",stdout);
	#endif
    ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int test_case;
	test_case=1;
	cin>>test_case;
	while(test_case--) 
    solve();
	return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

input:

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

output:

0 0
-1 0
1 2

result:

ok T=3 (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 21ms
memory: 3476kb

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:

1 -100105486
250 250
125 125
250 248
125 124
50 50
125 123
250 244
125 122
250 242
25 25
250 240
125 120
250 238
125 119
50 94489260
125 118
250 234
125 117
250 232
25 24
250 230
125 115
250 228
125 114
10 10
125 113
250 224
125 112
250 222
25 23
250 220
125 110
250 218
125 109
50 44
125 108
250 214...

result:

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