QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#553136 | #2406. Venn Intervals | Xiao_Nanniang | AC ✓ | 2599ms | 71440kb | C++17 | 11.8kb | 2024-09-08 09:30:02 | 2024-09-08 09:30:04 |
Judging History
answer
#include <iostream>
#include <numeric>
#include <bitset>
#include <vector>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <chrono>
#include <random>
#include <cstring>
#define ll long long
#define ull unsigned long long
using namespace std;
mt19937_64 myRand64(chrono::steady_clock::now().time_since_epoch().count());
// unordered_map<ull, int> name;
// vector<pair<ull, int>> name;
unordered_map<string, int> idx;
vector<pair<ull, pair<int, int>>> pairwise;
// unordered_map<ull, pair<int, int>> pairwise;
vector<string> names;
vector<ull> values;
int m;
int n;
ull value3[4010];
// unordered_set<ull> haveValue3;
vector<ull> haveValue3;
vector<int> graph[4010];
ull vis[4010];
vector<vector<int>> lists;
pair<int, int> res[2010];
ull GetVal(const string& s) {
auto it = idx.find(s);
if (it == idx.end()) {
idx[s] = values.size();
ull key = myRand64();
// while (name.count(key)) {
// key = myRand64();
// }
// name[key] = values.size();
names.push_back(s);
values.push_back(key);
return key;
}
return values[it->second];
}
bool SearchList(int a) {
vis[a] = true;
lists.back().push_back(a);
if (graph[a].size() == 2) {
for (auto& x : graph[a]) {
if (!vis[x]) {
if (!SearchList(x)) {
return false;
}
break;
}
}
}
return true;
}
int Get(int a) {
if (res[a].first == -1) {
return 0;
}
if (res[a].second == -1) {
return 1;
}
return 2;
}
bool Check() {
for (int i = 0; i < m; i++) {
if (Get(i) != 2) {
return false;
}
}
vector<pair<int, int>> copy(res, res + m);
sort(copy.begin(), copy.end());
for (int i = 1; i < m; i++) {
if (copy[i].first <= copy[i - 1].first || copy[i].second <= copy[i - 1].second) {
return false;
}
}
return true;
}
bool AddEdge(int a, int b) {
graph[a].push_back(b);
graph[b].push_back(a);
if (graph[b].size() > 2 || graph[a].size() > 2) {
return false;
}
return true;
}
// int CountName(ull a) {
// return lower_bound(name.begin(), name.end(), (pair<ull, int>) { a + 1, 0 })
// - lower_bound(name.begin(), name.end(), (pair<ull, int>) { a, 0 });
// }
pair<int, int> FindPairwise(ull a) {
// cout << "Find " << endl;
auto it = lower_bound(pairwise.begin(), pairwise.end(), (pair<ull, pair<int, int>>) { a, { -1, -1 } });
// cout << it->first << endl;
if (it == pairwise.end() || it->first != a) {
// cout << a << " fail" << endl;
// cout << it->first << ',' << a << endl;
return { -1, -1 };
}
// cout << "success" << endl;
return it->second;
}
int CountVal3(ull a) {
auto [l, r] = equal_range(haveValue3.begin(), haveValue3.end(), a);
return r - l;
}
bool Res() {
for (int i = 0; i < n - 1; i++) {
bool base = (FindPairwise(value3[i]) != (pair<int, int>) { -1, -1 });
for (int j = i + 1; j < n; j++) {
auto key = FindPairwise(value3[i] - value3[j]);
if (key.first != -1 || key.second != -1) {
if (key.first == -1 || key.second == -1) {
if (!AddEdge(i, j)) {
return false;
}
continue;
}
if (!base) {
ull mid = value3[j] - values[key.second];
ull mid2 = value3[j] + values[key.first];
// cout << value3[i] << ',' << value3[j] - values[key.second] + values[key.first] << endl;
if (CountVal3(mid) == 0 && CountVal3(mid2) == 0) {
if (!AddEdge(i, j)) {
return false;
}
// cout << i << ',' << j << endl;
}
}
}
// if (graph[j].size() > 1) {
// continue;
// }
// auto it = lower_bound(pairwise.begin(), pairwise.end(), (pair<ull, pair<int, int>>) { value3[j] - value3[i], { 0, 0 } });
// // auto it = pairwise.find(value3[j] - value3[i]);
// if (it != pairwise.end() && it->first == value3[j] - value3[i]) {
// ull mid = value3[i] - values[it->second.second];
// ull mid2 = value3[i] + values[it->second.first];
// if (CountVal3(mid) == 0 && CountVal3(mid2) == 0) {
// if (!AddEdge(i, j)) {
// return false;
// }
// }
// }
}
}
// for (int i = 0; i < n; i++) {
// cout << i << ':';
// for (auto& x : graph[i]) {
// cout << x << ',';
// }
// cout << endl;
// }
// for (auto& x : graph) {
// for (auto& y : x) {
// cout << y << ',';
// }
// cout << endl;
// }
// cout << endl;
for (int i = 0; i < n; i++) {
if (graph[i].empty()) {
vis[i] = true;
lists.push_back({ i });
continue;
}
if (!vis[i] && graph[i].size() == 1) {
vis[i] = true;
lists.push_back({ i });
SearchList(graph[i][0]);
}
}
// for (auto& x : lists) {
// for (auto& y : x) {
// cout << y << ',';
// }
// cout << endl;
// }
for (int i = 0; i < n; i++) {
if (!vis[i]) {
return false;
}
}
int cc = 0;
for (auto& x : lists) {
int k = x.size();
// auto it = name.find(value3[x[0]]);
// if (it == name.end()) {
auto key = FindPairwise(value3[x[0]]);
if (key.first == -1 || key.second != -1) {
// cout << x[0] << endl;
// cout << value3[x[0]] << endl;
// cout << values[idx["A"]] << endl;
// cout << FindPairwise(value3[x[0]]).second << endl;
return false;
}
int cur = key.first;
if (Get(cur) != 0) {
return false;
}
res[cur].first = cc;
cc++;
for (int i = 1; i < k; i++) {
ull diff = value3[x[i]] - value3[x[i - 1]];
// it = name.find(diff);
// if (it != name.end()) {
key = FindPairwise(diff);
// cout << i << ',' << key.first << ',' << key.second << endl;
if (key.first == -1) {
if (key.second == -1) {
return false;
}
cur = key.second;
if (Get(cur) != 1) {
return false;
}
res[cur].second = cc;
cc++;
continue;
}
if (key.second == -1) {
cur = key.first;
if (Get(cur) != 0) {
return false;
}
res[cur].first = cc;
cc++;
continue;
}
if (Get(key.first) != 0 || Get(key.second) != 1) {
return false;
}
res[key.first].first = cc;
res[key.second].second = cc;
cc++;
continue;
// if (it != name.end() && it->first == diff) {
// cur = it->second;
// if (Get(cur) != 0) {
// return false;
// }
// res[cur].first = cc;
// cc++;
// continue;
// }
// // it = name.find(-diff);
// // if (it != name.end()) {
// it = lower_bound(name.begin(), name.end(), (pair<ull, int>) { -diff, 0 });
// if (it != name.end() && it->first == -diff) {
// cur = it->second;
// if (Get(cur) != 1) {
// return false;
// }
// res[cur].second = cc;
// cc++;
// continue;
// }
// // auto it2 = pairwise.find(diff);
// // if (it2 != pairwise.end()) {
// auto it2 = lower_bound(pairwise.begin(), pairwise.end(), (pair<ull, pair<int, int>>) { diff, { 0, 0 } });
// if (it2 != pairwise.end() && it2->first == diff) {
// auto cur2 = it2->second;
// if (Get(cur2.first) != 0 || Get(cur2.second) != 1) {
// return false;
// }
// res[cur2.first].first = cc;
// res[cur2.second].second = cc;
// cc++;
// continue;
// }
// return false;
}
// it = name.find(value3[x[k - 1]]);
// if (it == name.end()) {
key = FindPairwise(-value3[x[k - 1]]);
// it = lower_bound(name.begin(), name.end(), (pair<ull, int>) { value3[x[k - 1]], 0 });
// if (it == name.end() || it->first != value3[x[k - 1]]) {
if (key.first != -1 || key.second == -1) {
return false;
}
cur = key.second;
if (Get(cur) != 1) {
return false;
}
res[cur].second = cc;
cc++;
}
// cout << "Finish?" << endl;
return Check();
}
void Solve() {
string s;
cin >> n;
getline(cin, s);
// value3.resize(n);
// graph.resize(n);
// vis.resize(n);
for (int i = 0; i < n; i++) {
getline(cin, s);
s += ' ';
// istringstream ss(s);
int cc = s.find(' ');
// cout << s.substr(cc) << endl;
int k = stoi(s.substr(0, cc));
// cout << k << endl;
for (int j = 0; j < k; j++) {
int cc2 = s.find(' ', cc + 1);
string cur = s.substr(cc + 1, cc2 - cc - 1);
// cout << cur << endl;
cc = cc2;
value3[i] += GetVal(cur);
}
haveValue3.push_back(value3[i]);
}
sort(haveValue3.begin(), haveValue3.end());
// return;
// cout << values[idx["B"]] << '\n';
// cout << GetVal("B") << '\n';
// cout << (value3[0] ^ value3[1]) << endl;
m = values.size();
// name.resize(m);
for (int i = 0; i < m; i++) {
pairwise.push_back({ values[i], {i, -1} });
pairwise.push_back({ -values[i], {-1, i} });
// name[i] = { values[i], i };
}
// sort(name.begin(), name.end());
// cout << "m=" << m << endl;
memset(res, -1, sizeof(res));
// res.assign(m, { -1, -1 });
// cout << "fuck" << endl;
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (i != j) {
// pairwise[values[i] - values[j]] = { i, j };
pairwise.push_back({ values[i] - values[j], {i, j} });
}
}
}
// cout << pairwise.size() << endl;
sort(pairwise.begin(), pairwise.end());
// for (auto& [x, y] : pairwise) {
// cout << x << endl;
// }
// cout << "fuck" << endl;
// cout << "fuck" << endl;
if (!Res()) {
cout << "IMPOSSIBLE";
return;
}
for (int i = 0; i < m; i++) {
cout << names[i] << ' ' << res[i].first << ' ' << res[i].second << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// int T;
// cin >> T;
// for (int i = 1; i <= T; i++) {
Solve();
// cout << "Case #" << i << ": " << s2 << '\n';
// }
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3768kb
input:
1 1 A
output:
A 0 1
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
10 3 A E B 2 A E 1 D 2 C D 1 A 3 B F C 3 B E F 2 B F 2 C F 1 C
output:
A 7 10 E 6 9 B 4 8 D 0 2 C 1 5 F 3 7
result:
ok correct!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
5 1 A 2 A B 3 A B C 4 A B C D 5 A B C D E
output:
IMPOSSIBLE
result:
ok no solution
Test #4:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
98 1 J 1 R 2 R KB 3 I R KB 4 I R IB KB 5 I P R IB KB 6 D I P R IB KB 2 J NB 3 J L NB 4 J L W NB 5 J L W DB NB 6 J L M W DB NB 7 J L M S W DB NB 8 E J L M S W DB NB 9 E J L M S W AB DB NB 7 D I P R IB KB OB 8 D I O P R IB KB OB 9 D I O P R EB IB KB OB 9 D K O P R EB IB KB OB 10 D H K O P R EB IB KB O...
output:
IMPOSSIBLE
result:
ok no solution
Test #5:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
2 34 B C D E F H I J K L M N O S T V W X Y Z EB FB GB KB LB MB OB PB RB SB TB UB VB WB 32 A C E F G I J K L P Q R S U W AB BB CB DB EB HB IB JB KB LB MB NB QB SB UB VB XB
output:
IMPOSSIBLE
result:
ok no solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
12 1 A 2 A C 3 A B C 4 A B C D 3 A B D 2 B D 1 B 2 A E 3 A B E 4 A B E F 3 A B F 2 B F
output:
IMPOSSIBLE
result:
ok no solution
Test #7:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
52 2 a b 2 a c 2 a d 2 a e 2 a f 2 a g 2 a h 2 a i 2 a j 2 a k 2 a l 2 a m 2 a n 2 a o 2 a p 2 a q 2 a r 2 a s 2 a t 2 a u 2 a v 2 a w 2 a x 2 a y 2 a z 2 a A 2 a B 2 a C 2 a D 2 a E 2 a F 2 a G 2 a H 2 a I 2 a J 2 a K 2 a L 2 a M 2 a N 2 a O 2 a P 2 a Q 2 a R 2 a S 2 a T 2 a U 2 a V 2 a W 2 a X 1 b...
output:
IMPOSSIBLE
result:
ok no solution
Test #8:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
40 7 FB DB C PB O R GB 7 EB QB WB LB F U SB 7 FB DB P LB G R X 7 L B C A UB NB Z 7 FB QB WB LB F U SB 7 H KB C PB CB NB Z 7 BB T JB S I TB AB 7 FB DB C LB O R GB 7 FB DB C LB G R GB 7 FB DB Q LB G R X 7 H KB C W UB NB Z 7 BB T JB S RB E AB 7 H J C PB O NB Z 7 BB T JB S RB TB AB 7 FB DB WB LB G U SB ...
output:
IMPOSSIBLE
result:
ok no solution
Test #9:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
73 3 AB H NB 3 AB NB CB 3 AB H KB 3 AB NB JB 2 AB FB 3 AB BB OB 4 AB H PB B 3 AB H B 3 AB WB Z 3 AB GB N 3 AB GB F 3 AB T Y 2 AB LB 2 AB KB 4 AB GB I V 3 AB H K 3 AB KB EB 3 AB T UB 3 AB WB LB 2 AB GB 2 AB Y 3 AB GB E 2 AB T 3 AB H QB 2 AB WB 2 AB TB 4 AB H KB O 3 AB E HB 2 AB CB 4 AB H NB XB 4 AB H...
output:
IMPOSSIBLE
result:
ok no solution
Test #10:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
81 7 Z QB F EB PB IB RB 21 Z QB F EB PB IB RB CB W VB B S AB DB E MB T LB J G GB 16 Z QB F EB PB IB RB CB W VB B S AB DB E MB 32 Z QB F EB PB IB RB CB W VB B S AB DB E MB T LB J M G KB X NB HB D C JB Q BB A H 17 Z QB F EB PB IB RB CB W VB B S AB DB E T Y 20 Z QB F EB PB IB RB CB W VB B S AB DB E MB ...
output:
IMPOSSIBLE
result:
ok no solution
Test #11:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
9 1 A 2 A B 1 B 2 A C 3 A C D 2 C D 1 D 1 E 1 F
output:
A 1 5 B 0 2 C 3 6 D 4 7 E 8 9 F 10 11
result:
ok correct!
Test #12:
score: 0
Accepted
time: 478ms
memory: 21148kb
input:
1999 328 KO WFB AKB UE NJB BM UIB AK OZ QT FV AE ZM RB ZN UKB OQ SV EP RZ GBB QG VJ LE QP SU OH OU WI GU UI VH EK KT VGB NLB GLB BJ K ZY NV QHB CBB AQ TL GN BZ ZI XIB MX GO HB EGB KD THB EO DM REB YT CY RO CCB OR ON RD TKB QIB CK DV IIB ZT TB QX OP LL AM WC WE DR VC UQ AC OL SG DG VB FQ KEB MDB WY H...
output:
KO 672 1672 WFB 673 1673 AKB 674 1674 UE 675 1675 NJB 676 1676 BM 677 1677 UIB 678 1678 AK 679 1679 OZ 680 1680 QT 681 1681 FV 682 1682 AE 683 1683 ZM 684 1684 RB 685 1685 ZN 686 1686 UKB 687 1687 OQ 688 1688 SV 689 1689 EP 690 1690 RZ 691 1691 GBB 692 1692 QG 693 1693 VJ 694 1694 LE 695 1695 QP 696...
result:
ok correct!
Test #13:
score: 0
Accepted
time: 505ms
memory: 70896kb
input:
2000 1999 BAAAAAAAAA CAAAAAAAAA DAAAAAAAAA EAAAAAAAAA FAAAAAAAAA GAAAAAAAAA HAAAAAAAAA IAAAAAAAAA JAAAAAAAAA KAAAAAAAAA LAAAAAAAAA MAAAAAAAAA NAAAAAAAAA OAAAAAAAAA PAAAAAAAAA QAAAAAAAAA RAAAAAAAAA SAAAAAAAAA TAAAAAAAAA UAAAAAAAAA VAAAAAAAAA WAAAAAAAAA XAAAAAAAAA YAAAAAAAAA ZAAAAAAAAA ABAAAAAAAA BBAA...
output:
IMPOSSIBLE
result:
ok no solution
Test #14:
score: 0
Accepted
time: 2599ms
memory: 71440kb
input:
3999 1488 OH OW DFB PK XZB AEB EKB JZ IU RLB YDC ZEC MSC TQC F WTC BPC KOC CXC XWC LL UHB MNC FPB WSB FOB RUC CPC SK GX VPC XPC BL SLC PRB GJC AHB ZZ EL PDC DSB MUC UQ NGC LX HC O NVB MKB OM NQ KH GSB TIB RGC TBC NWC OXB DF OIB OZB ICB ZGC DDB LWB YI XZ PNB NHC BGC RY RL QMB KSB GH IOB SVB GHB CV FC...
output:
OH 1487 3487 OW 1486 3486 DFB 1485 3485 PK 1484 3484 XZB 1483 3483 AEB 1482 3482 EKB 1481 3481 JZ 1480 3480 IU 1479 3479 RLB 1478 3478 YDC 1477 3477 ZEC 1476 3476 MSC 1475 3475 TQC 1474 3474 F 1473 3473 WTC 1472 3472 BPC 1471 3471 KOC 1470 3470 CXC 1469 3469 XWC 1468 3468 LL 1467 3467 UHB 1466 3466 ...
result:
ok correct!
Test #15:
score: 0
Accepted
time: 891ms
memory: 69460kb
input:
2001 2 STC KOB 2 QKC ASB 2 PF WD 2 KJC IBC 2 OX DL 2 IAC LXC 2 UGB BZ 2 SB XFC 2 CCC OIB 2 LQB UMC 2 TGB HGB 2 RFB OYB 2 DXB CQ 2 ELC SJB 2 UO VVB 2 WLB T 2 AM UY 2 LTC GKC 2 ZVB ASC 2 FVB CY 2 AOC I 2 OC SOB 2 JIC IYB 2 NRC HYC 2 TZ MB 2 KKC AG 2 JM EMB 2 XAC WBC 2 CMB VIC 2 IV UR 2 CIC GNC 2 ONC I...
output:
STC 482 484 KOB 483 485 QKC 1881 1883 ASB 1882 1884 PF 183 185 WD 184 186 KJC 1679 1681 IBC 1680 1682 OX 792 794 DL 793 795 IAC 532 534 LXC 533 535 UGB 662 664 BZ 663 665 SB 167 169 XFC 168 170 CCC 373 375 OIB 374 376 LQB 1193 1195 UMC 1194 1196 TGB 1229 1231 HGB 1230 1232 RFB 1841 1843 OYB 1842 184...
result:
ok correct!
Test #16:
score: 0
Accepted
time: 902ms
memory: 70120kb
input:
2000 1 VIC 1 ND 1 MYC 1 UGB 1 YMC 1 OF 1 FZ 1 XGB 1 NSC 1 BMC 1 JWC 1 URB 1 KFC 1 HUB 1 VOC 1 AWB 1 SVC 1 UKC 1 POB 1 QV 1 QJC 1 GMC 1 LQC 1 AJC 1 QX 1 LX 1 ETC 1 MUC 1 IXC 1 RGB 1 YS 1 HIB 1 GUB 1 UCC 1 UIC 1 ODC 1 HAB 1 WM 1 FH 1 ZCB 1 IVC 1 TMC 1 YEC 1 NS 1 OHB 1 SHB 1 GCB 1 PVC 1 MGC 1 QL 1 ZMB ...
output:
VIC 0 1 ND 2 3 MYC 4 5 UGB 6 7 YMC 8 9 OF 10 11 FZ 12 13 XGB 14 15 NSC 16 17 BMC 18 19 JWC 20 21 URB 22 23 KFC 24 25 HUB 26 27 VOC 28 29 AWB 30 31 SVC 32 33 UKC 34 35 POB 36 37 QV 38 39 QJC 40 41 GMC 42 43 LQC 44 45 AJC 46 47 QX 48 49 LX 50 51 ETC 52 53 MUC 54 55 IXC 56 57 RGB 58 59 YS 60 61 HIB 62 ...
result:
ok correct!
Test #17:
score: 0
Accepted
time: 1002ms
memory: 69960kb
input:
2200 2 WW YH 1 SSC 2 CL DX 2 WT AWB 2 EWB KXB 2 SRB BBB 2 VLB MRC 2 DJC ONC 2 MUB QL 2 TW EYC 2 XK QLC 1 CIB 2 QNB CRB 1 WOB 1 ZDC 2 MNB TTC 2 VX TUB 2 EIC OW 2 VQB O 1 QYB 1 LWC 2 OFC CXB 1 OT 2 QY ZIB 2 GQ RVC 2 LC BR 2 XCC TMC 2 VVC ZVC 2 IIB ZCC 2 PFB RKB 1 CT 2 MZB OKB 2 XD ZP 1 NXB 2 IEB JNB 2...
output:
WW 824 826 YH 825 827 SSC 0 2 CL 1662 1664 DX 1663 1665 WT 1469 1471 AWB 1470 1472 EWB 1886 1888 KXB 1885 1887 SRB 1517 1519 BBB 1518 1520 VLB 2085 2087 MRC 2086 2088 DJC 2371 2373 ONC 2370 2372 MUB 1651 1653 QL 1652 1654 TW 593 595 EYC 592 594 XK 73 75 QLC 74 76 CIB 12 14 QNB 1903 1905 CRB 1902 190...
result:
ok correct!
Test #18:
score: 0
Accepted
time: 1326ms
memory: 69440kb
input:
3013 987 USC UQB QUC VBB VTC GPC TGB HIC JQ KBC FD APC EXC NP XQB OVB VKB FOB FGC AE LQC PG NN STB ZSC LVC KPC DBC URB QGC DMB EOB V ANB OIC UN HD RG GYB CLB KMC QFC VHB KV AGB GF DYB AGC XC YUC VRC UTC NV LQ ZBB XMB MVB YQB IR FJC JH JI TN FMC LFC UYB ZHC UDB QKC XTB QQB IQ SOC LNC NCB SLB LV ZMB B...
output:
IMPOSSIBLE
result:
ok no solution
Test #19:
score: 0
Accepted
time: 2446ms
memory: 71128kb
input:
3982 12 SLC TEC YDB TRB TR GK BY EOB JIC YI BVB OPC 14 GR ZH OX BZB KPC TYC OVB PMC MYB YXC SGB QSB WS YEC 20 MF JS CYC ORC JAC UUB UTB NMB BNC CVB DWB GQ FL INC WMB CAB ZK BZ CE IXB 28 QVC VLB RCB MOB HXB SLB ZSB OK YMC XOC EC RSB NTB LKB E BBB OKC DT VBB NS EYB DIC INB JY G BIC NP BYB 24 WUC OAB S...
output:
IMPOSSIBLE
result:
ok no solution
Test #20:
score: 0
Accepted
time: 2210ms
memory: 71180kb
input:
3899 51 HP AMB SNC YJ RMB TTB SSB QBC JH GK BPC FYC KJ IJ ZTC PIC FJ LMC VTB KG MDB NMC EKC YAC HD OD JJC GB SHC P HWB XK MS TGC VC SE SC QLB NBB QEC DUC VB GBC FPB O AXC SRB OCB RVC CSB GRC 14 QZ XMC BGB EN JLC QX AGB IOB OSC WCC BVC BHB GMC LBB 56 PIC FJ LMC VTB KG MDB NMC EKC YAC HD OD JJC GB SHC...
output:
IMPOSSIBLE
result:
ok no solution
Test #21:
score: 0
Accepted
time: 2232ms
memory: 69884kb
input:
3888 35 OPC ZCC KPC TY RNB TS TOB QG BEB CIC ARB TC GAB MXC JVB LNB RH YE HNC IQB VV ETC WW CGB HDC NM YDB WT PXC JZ MEB KVC GE OTB CRC 5 WLC IB EI ASB RLC 5 LO EE DG LL FHC 8 RKB WRB WSB LR MY UEB TYB DJB 6 X YDC BD MQ M EHB 14 PDC HUC MBB CJB ASC OWC AW VCC UYC JG QKC TGB POC YL 25 VY IGB PHC GGC ...
output:
OPC 2588 2653 ZCC 2589 2657 KPC 2590 2666 TY 2591 2667 RNB 2592 2668 TS 2593 2669 TOB 2595 2670 QG 2596 2671 BEB 2597 2673 CIC 2598 2674 ARB 2599 2675 TC 2602 2676 GAB 2607 2677 MXC 2608 2679 JVB 2610 2684 LNB 2612 2686 RH 2613 2688 YE 2616 2689 HNC 2617 2692 IQB 2618 2694 VV 2620 2698 ETC 2623 2699...
result:
ok correct!
Test #22:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 2 A B 2 B C 2 C A
output:
IMPOSSIBLE
result:
ok no solution
Test #23:
score: 0
Accepted
time: 2274ms
memory: 70656kb
input:
3972 20 GDB ZN RMC P MAB OE CQ MKC LV NRC NO HJ BZ NM IWC ADB GYB ZS ORB PDC 49 DWB ASB XZ CJ QAC OF MBB HD OB QWC FJC LSB DKC CN UM RTC KXC UL OZB L IPB DSB XYB LVB NBC OIC AKB TOC YV WIB WZ UQ KVB BS GTB WIC FUB UIB SOC KYC ZX PPC TRB JAC PZB GFC KZB BOB AFB 27 BW PE EDC QHB IIC BXC RXC EQ UBB NQ ...
output:
GDB 2149 2193 ZN 2154 2196 RMC 2157 2199 P 2158 2202 MAB 2161 2203 OE 2162 2205 CQ 2164 2207 MKC 2165 2209 LV 2170 2212 NRC 2172 2214 NO 2175 2215 HJ 2176 2218 BZ 2177 2220 NM 2178 2222 IWC 2179 2225 ADB 2181 2229 GYB 2184 2230 ZS 2185 2231 ORB 2186 2234 PDC 2189 2235 DWB 777 858 ASB 778 860 XZ 779 ...
result:
ok correct!
Test #24:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
8 3 A C D 1 B 2 A C 1 E 1 D 1 A 2 A B 1 F
output:
IMPOSSIBLE
result:
ok no solution
Test #25:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
8 1 F 1 A 3 A C D 1 B 1 E 2 A B 1 D 2 A C
output:
IMPOSSIBLE
result:
ok no solution
Test #26:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
8 1 B 3 A C D 1 F 2 A C 1 E 1 A 2 A B 1 D
output:
IMPOSSIBLE
result:
ok no solution
Test #27:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
8 1 D 1 B 2 A C 1 A 3 A C D 1 F 2 A B 1 E
output:
IMPOSSIBLE
result:
ok no solution
Test #28:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
8 1 A 1 F 3 A C D 1 D 2 A C 2 A B 1 B 1 E
output:
IMPOSSIBLE
result:
ok no solution
Test #29:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
8 1 B 1 F 3 A C D 2 A C 1 E 2 A B 1 A 1 D
output:
IMPOSSIBLE
result:
ok no solution
Test #30:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
8 1 D 2 A C 3 A C D 1 F 2 A B 1 A 1 E 1 B
output:
IMPOSSIBLE
result:
ok no solution
Test #31:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
8 1 D 1 B 2 A C 2 A B 1 F 3 A C D 1 A 1 E
output:
IMPOSSIBLE
result:
ok no solution
Test #32:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
8 1 A 2 A B 2 A C 1 B 1 F 3 A C D 1 D 1 E
output:
IMPOSSIBLE
result:
ok no solution
Test #33:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
8 1 A 2 A B 1 B 2 A C 3 A C D 1 D 1 E 1 F
output:
IMPOSSIBLE
result:
ok no solution
Test #34:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
8 2 A B 1 A 1 F 1 D 1 B 2 A C 1 E 3 A C D
output:
IMPOSSIBLE
result:
ok no solution
Test #35:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
8 1 A 1 D 3 A C D 1 E 2 A B 1 B 1 F 2 A C
output:
IMPOSSIBLE
result:
ok no solution
Test #36:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
8 3 A C D 2 A C 2 A B 1 F 1 D 1 A 1 B 1 E
output:
IMPOSSIBLE
result:
ok no solution
Test #37:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
8 1 D 1 A 1 B 1 E 3 A C D 2 A B 2 A C 1 F
output:
IMPOSSIBLE
result:
ok no solution
Test #38:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
8 3 A C D 1 A 2 A C 1 F 1 B 1 E 1 D 2 A B
output:
IMPOSSIBLE
result:
ok no solution
Test #39:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
8 1 E 1 F 1 D 1 A 2 A C 1 B 3 A C D 2 A B
output:
IMPOSSIBLE
result:
ok no solution
Test #40:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
8 1 F 1 B 2 A B 1 E 1 A 3 A C D 2 A C 1 D
output:
IMPOSSIBLE
result:
ok no solution
Test #41:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
8 3 A C D 1 F 2 A C 1 D 1 A 2 A B 1 E 1 B
output:
IMPOSSIBLE
result:
ok no solution
Test #42:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
8 1 B 1 F 1 D 1 A 2 A C 3 A C D 2 A B 1 E
output:
IMPOSSIBLE
result:
ok no solution
Test #43:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
8 1 E 1 B 2 A C 1 A 1 F 2 A B 1 D 3 A C D
output:
IMPOSSIBLE
result:
ok no solution
Test #44:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
8 1 A 2 A C 1 F 3 A C D 1 E 2 A B 1 D 1 B
output:
IMPOSSIBLE
result:
ok no solution