QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#792166 | #9279. Matrix 4 | bulijiojiodibuliduo# | TL | 0ms | 3980kb | C++17 | 2.9kb | 2024-11-29 02:58:43 | 2024-11-29 02:58:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
array<ll,2> operator + (array<ll,2> a,array<ll,2> b) {
return {a[0]+b[0],a[1]+b[1]};
}
array<ll,2> operator - (array<ll,2> a,array<ll,2> b) {
return {a[0]-b[0],a[1]-b[1]};
}
array<ll,2> operator * (array<ll,2> a,ll c) {
return {a[0]*c,a[1]*c};
}
ll p,q,r,s;
int M=1000000000;
bool solve() {
scanf("%lld%lld%lld%lld",&p,&q,&r,&s);
if (p*s-q*r!=1) return false;
if ((p-1)%4!=0||(s-1)%4!=0) return false;
if (q%2!=0||r%2!=0) return false;
array<ll,2> a{p,r},b{q,s};
vector<string> opr;
auto opB=[&](int tt=1){
a=a+b*(2*tt);
if (tt==1) opr.pb("B");
else opr.pb("(B)"+to_string(tt));
};
auto opA=[&](int tt=1){
b=b+a*(2*tt);
if (tt==1) opr.pb("A");
else opr.pb("(A)"+to_string(tt));
};
auto opa=[&](int tt=1){
b=b-a*(2*tt);
if (tt==1) opr.pb("a");
else opr.pb("(a)"+to_string(tt));
};
auto opb=[&](int tt=1){
a=a-b*(2*tt);
if (tt==1) opr.pb("b");
else opr.pb("(b)"+to_string(tt));
};
auto sgn=[&](ll a) {
return a>0?1:(a==0?0:-1);
};
auto gaoop=[&](string a,ll t) {
if (t<=M) opr.pb("("+a+")"+to_string(t));
else {
string v1="(("+a+")"+to_string(M)+")"+to_string(t/M);
if (t%M!=0) v1+="("+a+")"+to_string(t%M);
}
};
while (b[0]!=0) {
if (abs(a[0])>abs(b[0])) {
if (sgn(a[0])==sgn(b[0])) {
if (abs(a[0])>=2*abs(b[0])) {
opb(abs(a[0])/(2*abs(b[0])));
} else if (abs(a[0])>=4*abs(a[0]-b[0])) {
auto dt=a-b;
ll t=abs(a[0])/abs(a[0]-b[0])/4;
gaoop("bAbA",t);
a=a-dt*t; b=b-dt*t;
} else {
opb();
}
} else {
opB();
}
} else {
if (sgn(a[0])==sgn(b[0])) {
if (abs(b[0])>=2*abs(a[0])) {
opa(abs(b[0])/(2*abs(a[0])));
} else if (abs(b[0])>=4*abs(b[0]-a[0])) {
auto dt=b-a;
ll t=abs(b[0])/abs(b[0]-a[0])/4;
gaoop("aBaB",t);
a=a-dt*t; b=b-dt*t;
} else {
opa();
}
} else opA();
}
}
assert(a[0]==1&&b[1]==1);
if (a[1]>0) {
gaoop("b",a[1]/2);
} else if (a[1]<0) {
gaoop("B",-a[1]/2);
}
reverse(all(opr));
string s;
for (auto o:opr) s+=o;
puts(s.c_str());
// [p,r], [q,s]
return true;
}
int _;
int main() {
for (scanf("%d",&_);_;_--) {
if (!solve()) {
puts("Impossible");
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3752kb
input:
3 -7 4 -2 1 25 12 -48 -23 -1 0 0 1
output:
(a)2B (B)1(a)6b Impossible
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3980kb
input:
10 1 8 0 1 -7 2 -4 1 1 10 0 1 1 8 0 1 1 6 0 1 -7 2 -4 1 1 8 0 1 -3 2 -2 1 9 2 4 1 5 2 2 1
output:
(a)4 aBB (a)5 (a)4 (a)3 aBB (a)4 aB a(b)2 ab
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
10 -7 -4 6 5 9 -8 8 9 -3 4 -10 -3 -3 -4 0 -7 5 -2 8 -7 9 6 10 5 -11 8 2 -3 1 8 -10 1 -7 4 -4 5 1 10 0 -3
output:
Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
10 -5 7 2 -3 -7 1 -1 0 -4 -7 1 2 -8 -1 -1 0 3 -10 -1 3 -1 6 0 -1 6 -1 -1 0 -7 8 -1 1 -1 9 0 -1 3 -5 1 -2
output:
Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
10 4 -3 0 -5 -9 -9 -3 -10 -3 -8 1 -4 2 5 -3 -2 5 -1 -7 -3 -7 6 6 9 -5 -2 6 -7 2 -6 2 2 0 4 1 0 -2 -3 0 7
output:
Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible
result:
ok ok
Test #6:
score: -100
Time Limit Exceeded
input:
100 997 998 -998 -999 997 998 -998 -999 -999 -998 998 997 997 -998 998 -999 -999 -998 998 997 -999 998 -998 997 -999 -998 998 997 -999 998 -998 997 -999 -998 998 997 -999 -998 998 997 -999 -998 998 997 997 -998 998 -999 997 998 -998 -999 -999 998 -998 997 -999 998 -998 997 997 998 -998 -999 -999 -99...