#803729 (C) No.2107 Entangled LIS

提出ソース

結果

問題	No.2107 Entangled LIS
ユーザー	👑 ygussany
提出日時	2022-10-02 20:31:03
言語	C (gcc 12.3.0)
結果	AC
実行時間	40 ms / 2,000 ms
コード長	8,894 bytes
コンパイル時間	767 ms
コンパイル使用メモリ	37,408 KB
実行使用メモリ	6,224 KB
最終ジャッジ日時	2023-08-26 18:14:26
合計ジャッジ時間	2,877 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	33 ms 4,376 KB
testcase_02	AC	33 ms 4,376 KB
testcase_03	AC	19 ms 4,380 KB
testcase_04	AC	23 ms 4,376 KB
testcase_05	AC	34 ms 4,376 KB
testcase_06	AC	35 ms 4,376 KB
testcase_07	AC	36 ms 4,376 KB
testcase_08	AC	40 ms 6,224 KB
testcase_09	AC	36 ms 4,380 KB
testcase_10	AC	22 ms 5,012 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード