結果
| 問題 |
No.2107 Entangled LIS
|
| コンテスト | |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2022-10-02 20:31:03 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 49 ms / 2,000 ms |
| コード長 | 8,894 bytes |
| コンパイル時間 | 680 ms |
| コンパイル使用メモリ | 38,284 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-25 18:12:10 |
| 合計ジャッジ時間 | 3,016 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
ソースコード
#include <stdio.h>
int solve(int N, int A, int B, char s[], int a[], int b[])
{
int i, j, k, l, x, y;
static int sum[200003];
if (A == B) {
for (i = 1; i <= A; i++) {
a[i] = (N - A + i) * 2;
b[i] = a[i];
if (s[i] == 'a') b[i]--;
else a[i]--;
}
for (; i <= N; i++) {
a[i] = (N - i + 1) * 2;
b[i] = a[i];
if (s[i] == 'a') b[i]--;
else a[i]--;
}
} else if (A > B) {
if (B == 1) {
for (i = 1, k = 0; i <= N; i++) if (s[i] == 'a') k++;
if (k >= A) {
for (i = 1, y = N * 2; s[i] == 'b'; i++) {
b[i] = y--;
a[i] = y--;
}
for (k = 0, x = y - A + 1, y = x - 1; i <= N; i++) {
if (s[i] == 'b') {
b[i] = y--;
a[i] = y--;
} else if (k == A) {
a[i] = y--;
b[i] = y--;
} else {
k++;
a[i] = x++;
b[i] = y--;
}
}
} else if (N - k >= A) {
for (i = 1, y = N * 2; s[i] == 'a'; i++) {
a[i] = y--;
b[i] = y--;
}
for (k = 1, x = 1; i <= N; i++) {
if (s[i] == 'a') {
a[i] = y--;
b[i] = y--;
} else if (k == A) {
b[i] = y--;
a[i] = y--;
} else {
k++;
a[i] = x++;
b[i] = y--;
}
}
} else {
for (i = N, sum[N+1] = 0; i >= 1; i--) {
sum[i] = sum[i+1];
if (s[i] == 'a') sum[i]++;
}
for (i = 1, k = 0; i <= N; i++) {
if (s[i] == 'b') {
k++;
if (s[i+1] != 'b' && k + sum[i] >= A) break;
}
}
if (i > N) return 0;
for (l = i, i = 1, x = 1, y = N * 2; i <= l; i++) {
if (s[i] == 'a') {
a[i] = y--;
b[i] = y--;
} else {
a[i] = x++;
b[i] = y--;
}
}
for (x = y - (A - k) + 1, y = x - 1; i <= N; i++) {
if (s[i] == 'b') {
b[i] = y--;
a[i] = y--;
} else if (k == A) {
a[i] = y--;
b[i] = y--;
} else {
k++;
a[i] = x++;
b[i] = y--;
}
}
}
} else {
for (i = 1, x = 1; B > 2; i++, A--, B--) {
if (s[i] == 'a') {
b[i] = x++;
a[i] = x++;
} else {
a[i] = x++;
b[i] = x++;
}
}
for (l = i, k = 0, y = N * 2; i <= N; i++) {
if (s[i] == 'a') k++;
else b[i] = y--;
}
for (i = l, x += k - 1; i <= N; i++) if (s[i] == 'a') b[i] = x--;
for (i = l, x += k + 1; i <= N; i++) {
if (A > 1) {
A--;
a[i] = x++;
} else if (A == 1) {
A--;
a[i] = y--;
} else a[i] = y--;
}
for (i = l; i < N; i++) if (b[i] < b[i+1]) break;
if (i == N) {
for (i = l; i < N; i++) if (s[i] == s[i+1]) break;
b[i] ^= b[i+1];
b[i+1] ^= b[i];
b[i] ^= b[i+1];
}
}
} else {
if (A == 1) {
for (i = 1, k = 0; i <= N; i++) if (s[i] == 'b') k++;
if (k >= B) {
for (i = 1, y = N * 2; s[i] == 'a'; i++) {
a[i] = y--;
b[i] = y--;
}
for (k = 0, x = y - B + 1, y = x - 1; i <= N; i++) {
if (s[i] == 'a') {
a[i] = y--;
b[i] = y--;
} else if (k == B) {
b[i] = y--;
a[i] = y--;
} else {
k++;
b[i] = x++;
a[i] = y--;
}
}
} else if (N - k >= B) {
for (i = 1, y = N * 2; s[i] == 'b'; i++) {
b[i] = y--;
a[i] = y--;
}
for (k = 1, x = 1; i <= N; i++) {
if (s[i] == 'b') {
b[i] = y--;
a[i] = y--;
} else if (k == B) {
a[i] = y--;
b[i] = y--;
} else {
k++;
b[i] = x++;
a[i] = y--;
}
}
} else {
for (i = N, sum[N+1] = 0; i >= 1; i--) {
sum[i] = sum[i+1];
if (s[i] == 'b') sum[i]++;
}
for (i = 1, k = 0; i <= N; i++) {
if (s[i] == 'a') {
k++;
if (s[i+1] != 'a' && k + sum[i] >= B) break;
}
}
if (i > N) return 0;
for (l = i, i = 1, x = 1, y = N * 2; i <= l; i++) {
if (s[i] == 'b') {
b[i] = y--;
a[i] = y--;
} else {
b[i] = x++;
a[i] = y--;
}
}
for (x = y - (B - k) + 1, y = x - 1; i <= N; i++) {
if (s[i] == 'a') {
a[i] = y--;
b[i] = y--;
} else if (k == B) {
b[i] = y--;
a[i] = y--;
} else {
k++;
b[i] = x++;
a[i] = y--;
}
}
}
} else {
for (i = 1, x = 1; A > 2; i++, A--, B--) {
if (s[i] == 'b') {
a[i] = x++;
b[i] = x++;
} else {
b[i] = x++;
a[i] = x++;
}
}
for (l = i, k = 0, y = N * 2; i <= N; i++) {
if (s[i] == 'b') k++;
else a[i] = y--;
}
for (i = l, x += k - 1; i <= N; i++) if (s[i] == 'b') a[i] = x--;
for (i = l, x += k + 1; i <= N; i++) {
if (B > 1) {
B--;
b[i] = x++;
} else if (B == 1) {
B--;
b[i] = y--;
} else b[i] = y--;
}
for (i = l; i < N; i++) if (a[i] < a[i+1]) break;
if (i == N) {
for (i = l; i < N; i++) if (s[i] == s[i+1]) break;
a[i] ^= a[i+1];
a[i+1] ^= a[i];
a[i] ^= a[i+1];
}
}
}
return 1;
}
int judge(int N, int A, int B, char s[], int a[], int b[])
{
int i;
static int appear[400001];
for (i = 1; i <= N * 2; i++) appear[i] = 0;
for (i = 1; i <= N; i++) {
if (s[i] == 'a' && a[i] < b[i]) return 0;
if (s[i] == 'b' && a[i] > b[i]) return 0;
if (a[i] < 1 || a[i] > N * 2 || appear[a[i]] != 0) return 0;
else appear[a[i]] = 1;
if (b[i] < 1 || b[i] > N * 2 || appear[b[i]] != 0) return 0;
else appear[b[i]] = 1;
}
int k, l, r, m;
static int dp[200001];
for (i = 1, k = 0, dp[0] = 0; i <= N; i++) {
l = 0;
r = k;
while (l < r) {
m = (l + r + 1) / 2;
if (dp[m] < a[i]) l = m;
else r = m - 1;
}
dp[l+1] = a[i];
if (l == k) k++;
}
if (k != A) return 0;
for (i = 1, k = 0, dp[0] = 0; i <= N; i++) {
l = 0;
r = k;
while (l < r) {
m = (l + r + 1) / 2;
if (dp[m] < b[i]) l = m;
else r = m - 1;
}
dp[l+1] = b[i];
if (l == k) k++;
}
if (k != B) return 0;
return 1;
}
int DFS(int N, int A, int B, char s[], int a[], int b[], int k, int appear[])
{
if (k > N) {
if (judge(N, A, B, s, a, b) != 0) return 1;
else return 0;
}
int i, j;
for (i = 1; i <= N * 2; i++) {
if (appear[i] != 0) continue;
appear[i] = 1;
for (j = i + 1; j <= N * 2; j++) {
if (appear[j] != 0) continue;
appear[j] = 1;
if (s[k] == 'a') {
a[k] = j;
b[k] = i;
} else {
a[k] = i;
b[k] = j;
}
if (DFS(N, A, B, s, a, b, k + 1, appear) != 0) return 1;
appear[j] = 0;
}
appear[i] = 0;
}
return 0;
}
int naive(int N, int A, int B, char s[], int a[], int b[])
{
int i;
static int appear[400001];
for (i = 1; i <= N * 2; i++) appear[i] = 0;
return DFS(N, A, B, s, a, b, 1, appear);
}
#define MT_N 624
#define MT_M 397
#define MT_MATRIX_A 0x9908b0dfUL
#define MT_UPPER_MASK 0x80000000UL
#define MT_LOWER_MASK 0x7fffffffUL
static unsigned int mt[MT_N];
static int mti = MT_N + 1;
void init_genrand(unsigned int s)
{
mt[0] = s & 0xffffffffUL;
for (mti = 1; mti < MT_N; mti++) {
mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
mt[mti] &= 0xffffffffUL;
}
}
unsigned int genrand()
{
unsigned int y;
static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A};
if (mti >= MT_N) {
int kk;
if (mti == MT_N + 1) init_genrand(5489UL);
for (kk = 0; kk < MT_N - MT_M; kk++) {
y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL];
}
for (; kk < MT_N - 1; kk++) {
y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL];
}
y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK);
mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL];
mti = 0;
}
y = mt[mti++];
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
return y;
}
int main()
{
int i, T, N, A, B, a[200001], b[200001];
char s[200003];
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &N, &A, &B);
scanf("%s", &(s[1]));
if (solve(N, A, B, s, a, b) == 0) printf("No\n");
else {
printf("Yes\n");
for (i = 1; i <= N; i++) printf("%d ", a[i]);
printf("\n");
for (i = 1; i <= N; i++) printf("%d ", b[i]);
printf("\n");
}
/*
N = 5;
A = genrand() % N + 1;
B = genrand() % N + 1;
for (i = 1, s[N+1] = 0; i <= N; i++) s[i] = 'a' + genrand() % 2;
if (solve(N, A, B, s, a, b) != 0 && judge(N, A, B, s, a, b) == 0) {
printf("%d %d %d\n", N, A, B);
printf("%s\n", &(s[1]));
for (i = 1; i <= N; i++) printf("%d ", a[i]);
printf("\n");
for (i = 1; i <= N; i++) printf("%d ", b[i]);
printf("\n");
}
if (solve(N, A, B, s, a, b) == 0 && naive(N, A, B, s, a, b) != 0) {
printf("%d %d %d\n", N, A, B);
printf("%s\n", &(s[1]));
for (i = 1; i <= N; i++) printf("%d ", a[i]);
printf("\n");
for (i = 1; i <= N; i++) printf("%d ", b[i]);
printf("\n");
}
*/
}
fflush(stdout);
return 0;
}