QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792164#9279. Matrix 4bulijiojiodibuliduo#WA 0ms3684kbC++172.9kb2024-11-29 02:51:282024-11-29 02:51:28

Judging History

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

  • [2024-11-29 02:51:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3684kb
  • [2024-11-29 02:51:28]
  • 提交

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){
		a=a-b*(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){
		b=b+a*(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])) {
					opA(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("AbAb",t);
					a=a-dt*t; b=b-dt*t;
				} else {
					opA();
				}
			} 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 opb();
		}
	}
	assert(a[0]==1&&b[1]==1);
	if (a[1]>0) {
		gaoop("A",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: 0
Wrong Answer
time: 0ms
memory: 3684kb

input:

3
-7 4 -2 1
25 12 -48 -23
-1 0 0 1

output:

(a)2B
(B)1(a)6A
Impossible

result:

wrong answer case 1: wrong matrix obtained: expected = (25, 12, -48, -23); actual = (1, 10, -2, -19)