QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#553136#2406. Venn IntervalsXiao_NanniangAC ✓2599ms71440kbC++1711.8kb2024-09-08 09:30:022024-09-08 09:30:04

Judging History

你现在查看的是最新测评结果

  • [2024-09-08 09:30:04]
  • 评测
  • 测评结果:AC
  • 用时:2599ms
  • 内存:71440kb
  • [2024-09-08 09:30:02]
  • 提交

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

详细

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