Submission #3426001

---

Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "vector"
#include "string"
#include "map"
#include "algorithm"
#include "functional"
#include "set"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> K;
	vector<string>ans;
	for (int loop = 0; loop < K; loop++) {
		cin >> N >> M >> L >> R;
		if (N == M || N == M + 1) {
			string ret;
			for (long long int i = L; i <= R; i++) {
				if (i % 2)ret.push_back('A');
				else ret.push_back('B');
			}
			ans.push_back(ret);
			continue;
		}
		if (N + 1 == M) {
			string ret;
			for (long long int i = L; i <= R; i++) {
				if (i % 2)ret.push_back('B');
				else ret.push_back('A');
			}
			ans.push_back(ret);
			continue;
		}
		long long int k = max(N, M) / (min(N, M) + 1) + !!(max(N, M) % (min(N, M) + 1));
		long long int l = max(N, M) / k + !!(max(N, M) % k) - 1;
		long long int r = min(N, M);
		//cout << k << " " << l << " " << r << endl;
		if (r > l) {
			while (r - l > 1) {
				long long int mid = (l + r + 1) / 2;
				long long int anum = N - mid;
				anum /= (k - 1);
				anum++;
				long long int bnum = M - mid;
				bnum /= (k - 1);
				bnum = mid - bnum + 1;
			//	cout << mid << " " << anum << " " << bnum << endl;
				if ((bnum + 1 < anum) || (bnum + 1 == anum && (N - mid) % (k - 1)))l = mid;
				else r = mid;
			}
			long long int anum = N - r;
			anum /= (k - 1);
			anum++;
			long long int bnum = M - r;
			bnum /= (k - 1);
			if ((M - r) % (k - 1))bnum++;
			bnum = r - bnum + 1;
			//cout <<r<<" "<< anum << " " << bnum << endl;
			if (anum == bnum) {
				long long int f = (k + 1)*(anum - 1);
				long long int s = f + 1 + 1 + (N - r) % (k - 1) + (M - r) % (k - 1);
				string ret;
				for (int m = L; m <= min(R, f); m++) {
					if ((f - m) % (k + 1))ret.push_back('A');
					else ret.push_back('B');
				}
				for (int m = max(L,f + 1); m <= min(R, s); m++) {
					if (m - f <= 1 + (N - r) % (k - 1))ret.push_back('A');
					else ret.push_back('B');
				}
				for (int m = max(L, s + 1); m <= min(R,N + M); m++) {
					if ((m - s - 1) % (k + 1))ret.push_back('B');
					else ret.push_back('A');
				}
				ans.push_back(ret);
			}
			else if (anum == bnum + 1 && (N - r) % (k - 1) == 0) {
				long long int f = (k + 1)*(anum - 1);
				long long int s = f + (M - r) % (k - 1);
				if ((M - r) % (k - 1) == 0)s += k - 1;
				//cout << "hoge " << f << " " << s << endl;
				string ret;
				for (int m = L; m <= min(R, f); m++) {
					if ((f - m) % (k + 1))ret.push_back('A');
					else ret.push_back('B');
				}
				for (int m = max(L, f + 1); m <= min(R, s); m++) {
					ret.push_back('B');
				}
				for (int m = max(L, s + 1); m <= min(R,N + M); m++) {
					if ((m - s - 1) % (k + 1))ret.push_back('B');
					else ret.push_back('A');
				}
				ans.push_back(ret);
			}
			else {
				cout << "Clash!!\n";
				return 0;
			}
			continue;
		}
		else {
			cout << "Clash\n";
			return 0;
		}
	}
	for (auto i : ans)cout << i << endl;
	return 0;
}

Submission Info

Judge Result