QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#443113#8523. Puzzle IIucup-team266#WA 1ms10000kbC++143.2kb2024-06-15 14:27:222024-06-15 14:27:24

Judging History

This is the latest submission verdict.

  • [2024-06-15 14:27:24]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 10000kb
  • [2024-06-15 14:27:22]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef array<int, 3> ai3;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 1e9 + 7;
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, ll p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 10010;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN], inv[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
	for(int i = 1; i <= n; ++i) inv[i] = mul(invfact[i], fact[i-1]);
}
int binom(int n, int m){ return (m < 0 || m > n) ? 0 : mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
template<typename T> inline void chmax(T &_a, T _b){ (_a<_b) ? (_a=_b) : 0; }
template<typename T> inline void chmin(T &_a, T _b){ (_b<_a) ? (_a=_b) : 0; }
mt19937_64 rng(58);
inline int myrand(int l, int r){ return (int)(rng() % (r-l+1)) + l; }

int n, k;
int a[300300], b[300300];
int apre[300300], anxt[300300], bpre[300300], bnxt[300300];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> k;
	{
		string s;
		cin >> s;
		rep(i, n) a[i] = (s[i] == 'C');
	}
	{
		string s;
		cin >> s;
		rep(i, n) b[i] = (s[i] == 'C');
	}

	int c1 = 0;
	rep(i, n) c1 += a[i];
	if(c1 > (n/2)){
		rep(i, n) a[i] ^= 1, b[i] ^= 1;
		c1 = n - c1;
	}

	rep(i, n) apre[i] = bpre[i] = (i + n - 1) % n, anxt[i] = bnxt[i] = (i + 1) % n;

	vector<pii> ans;
	int ap0 = 0, apk = k-1, aid = 0, bp0 = 0, bpk = k-1, bid = 0;
	while(c1--){
		while(a[ap0] != 1) ap0 = anxt[ap0], apk = anxt[apk], aid = (aid + 1) % n;
		while(b[bnxt[bpk]] != 0) bp0 = bnxt[bp0], bpk = bnxt[bpk], bid = (bid + 1) % n;
		ans.push_back(make_pair(aid, bid)), ans.push_back(make_pair(aid, (bid + 1) % n));
		swap(a[ap0], b[bnxt[bpk]]);
		{
			int nap0 = anxt[ap0], napk = ap0;
			anxt[apre[ap0]] = anxt[ap0], apre[anxt[ap0]] = apre[ap0];
			apre[ap0] = apk, anxt[ap0] = anxt[apk];
			apre[anxt[apk]] = ap0, anxt[apk] = ap0;
			ap0 = nap0, apk = napk;
		}
		{
			int nbp0 = bnxt[bpk], nbpk = bpre[bpk];
			bpk = bnxt[bpk];
			bnxt[bpre[bpk]] = bnxt[bpk], bpre[bnxt[bpk]] = bpre[bpk];
			bpre[bpk] = bpre[bp0], bnxt[bpk] = bp0;
			bnxt[bpre[bp0]] = bpk, bpre[bp0] = bpk;
			bpk = nbp0, bpk = nbpk;
		}
	}

	cout << (int)ans.size() << "\n";
	rep(i, (int)ans.size()) cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 9776kb

input:

6 3
BCCBCC
BBCBBC

output:

4
1 3
1 4
4 1
4 2

result:

ok moves = 4

Test #2:

score: 0
Accepted
time: 1ms
memory: 10000kb

input:

2 1
BC
BC

output:

2
2 2
2 1

result:

ok moves = 2

Test #3:

score: 0
Accepted
time: 0ms
memory: 9928kb

input:

2 1
BB
CC

output:

0

result:

ok moves = 0

Test #4:

score: 0
Accepted
time: 1ms
memory: 7960kb

input:

2 1
CC
BB

output:

0

result:

ok moves = 0

Test #5:

score: 0
Accepted
time: 0ms
memory: 7772kb

input:

3 1
CCC
BBB

output:

0

result:

ok moves = 0

Test #6:

score: 0
Accepted
time: 0ms
memory: 7924kb

input:

3 1
CBC
BCB

output:

2
2 1
2 2

result:

ok moves = 2

Test #7:

score: 0
Accepted
time: 1ms
memory: 7956kb

input:

3 2
BBB
CCC

output:

0

result:

ok moves = 0

Test #8:

score: 0
Accepted
time: 1ms
memory: 9712kb

input:

3 2
BCB
BCC

output:

2
2 2
2 3

result:

ok moves = 2

Test #9:

score: 0
Accepted
time: 1ms
memory: 9992kb

input:

4 2
CCCB
BBCB

output:

2
4 1
4 2

result:

ok moves = 2

Test #10:

score: 0
Accepted
time: 1ms
memory: 9812kb

input:

9 6
CCCBCCCBB
BBBCBBBCC

output:

6
4 2
4 3
7 3
7 4
7 9
7 1

result:

ok moves = 6

Test #11:

score: -100
Wrong Answer
time: 1ms
memory: 7740kb

input:

21 3
CCCCBBCBCCCCCCCBCCCCC
BBCCBCBBBBBBBBBCBBBBB

output:

8
5 1
5 2
5 1
5 2
8 3
8 4
16 14
16 15

result:

wrong answer The final sequences are not correct!