結果
| 問題 | No.3798 algo to goal |
| コンテスト | |
| ユーザー |
tnakao0123
|
| 提出日時 | 2026-11-17 10:51:11 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 63 ms / 2,000 ms |
| + 752µs | |
| コード長 | 1,933 bytes |
| 記録 | |
| コンパイル時間 | 416 ms |
| コンパイル使用メモリ | 81,728 KB |
| 実行使用メモリ | 15,376 KB |
| 最終ジャッジ日時 | 2026-11-17 10:51:18 |
| 合計ジャッジ時間 | 7,270 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge4_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 40 |
ソースコード
/* -*- coding: utf-8 -*-
*
* 3798.cc: No.3798 algo to goal - yukicoder
*/
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
/* constant */
const int MAX_N = 1000000;
/* typedef */
using ll = long long;
using vi = vector<int>;
template <typename T>
struct BIT {
int n;
vector<T> bits;
BIT() {}
BIT(int _n) { init(_n); }
void init(int _n) {
n = _n;
bits.assign(n + 1, 0);
}
T sum(int x) {
x = min(x, n);
T s = 0;
while (x > 0) {
s += bits[x];
x -= (x & -x);
}
return s;
}
void add(int x, T v) {
if (x <= 0) return;
while (x <= n) {
bits[x] += v;
x += (x & -x);
}
}
};
/* global variables */
char s[MAX_N + 4], t[MAX_N + 4];
/* subroutines */
vi extract(int n, char s[], int p) {
vi v;
for (int i = p; i < n; i += 2) v.push_back(s[i] - 'a');
return v;
}
vi anagram(vi v) {
vi av(26, 0);
for (auto u: v) av[u]++;
return av;
}
ll invcnt(vi v) {
BIT<int> bit;
bit.init(26);
ll sum = 0;
for (auto u: v) {
sum += bit.sum(26) - bit.sum(u);
bit.add(u + 1, 1);
}
return sum;
}
/* main */
int main() {
int tn;
scanf("%d", &tn);
while (tn--) {
scanf("%s%s", s, t);
int n = strlen(s);
auto sv0 = extract(n, s, 0);
auto sv1 = extract(n, s, 1);
auto tv0 = extract(n, t, 0);
auto tv1 = extract(n, t, 1);
auto asv0 = anagram(sv0);
auto asv1 = anagram(sv1);
auto atv0 = anagram(tv0);
auto atv1 = anagram(tv1);
if (asv0 != atv0 || asv1 != atv1) { puts("No"); continue; }
int maxc0 = *max_element(asv0.begin(), asv0.end());
int maxc1 = *max_element(asv1.begin(), asv1.end());
if (maxc0 > 1 || maxc1 > 1) { puts("Yes"); continue; }
ll sinv = invcnt(sv0) + invcnt(sv1);
ll tinv = invcnt(tv0) + invcnt(tv1);
if ((sinv & 1) == (tinv & 1)) puts("Yes");
else puts("No");
}
return 0;
}
tnakao0123