QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792166#9279. Matrix 4bulijiojiodibuliduo#TL 0ms3980kbC++172.9kb2024-11-29 02:58:432024-11-29 02:58:44

Judging History

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

  • [2024-11-29 02:58:44]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3980kb
  • [2024-11-29 02:58:43]
  • 提交

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...

output:


result: