QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404280 | #6812. Draw a triangle | jiajieshi | WA | 19ms | 3604kb | C++20 | 9.2kb | 2024-05-03 18:00:56 | 2024-05-03 18:00:56 |
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];
const int len=10000;
if(Y[1]>Y[2])
{
swap(X[1],X[2]);
swap(Y[1],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 ansx,ansy;
ll x0=X[2]-X[1];
ll y0=Y[2]-Y[1];
ecgcd(x0,-y0,ansx,ansy);
ansy=(ansy%y0+y0)%y0 ;
ansx =(ansx%x0+x0)%x0;
cout <<X[1]+ansx << ' '<<Y[1]+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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3588kb
input:
3 1 0 1 4 0 1 0 9 0 0 2 2
output:
0 0 -1 0 0 1
result:
ok T=3 (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 19ms
memory: 3604kb
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:
66620223 -33485264 43307637 98028995 -88895479 -3181029 -90319913 20018431 -56783446 84789502 -81798287 90628903 98942736 -939348 -42532297 -57203611 53499987 -30665816 27114911 46989004 -2657661 26865224 40614019 17923272 -47650134 96037494 92954118 -64535078 86508632 -51415384 -82017934 17392356 7...
result:
wrong answer wa on query #4 (test case 4)