QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#404261 | #6812. Draw a triangle | jiajieshi | WA | 21ms | 3612kb | C++20 | 9.2kb | 2024-05-03 17:20:28 | 2024-05-03 17:20:28 |
Judging History
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)