— Dark mode

Putka Open 2025 – 1/5

Järjestys

  • Start: 2025-09-05 18:00:00
  • End: 2025-09-07 23:00:00
Submission details
Task:Järjestys
Sender:jlaire
Submission time:2025-09-07 02:01:43 +0300
Language:C++ (C++17)
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 4, 5details
#2ACCEPTED0.00 s1, 4, 5details
#3ACCEPTED0.01 s1, 4, 5details
#4ACCEPTED0.01 s1, 4, 5details
#5ACCEPTED0.01 s1, 4, 5details
#6ACCEPTED0.01 s1, 2, 4, 5details
#7ACCEPTED0.01 s1, 3, 4, 5details
#8ACCEPTED0.01 s1, 4, 5details
#9ACCEPTED0.38 s2, 4, 5details
#100.48 s3, 4, 5details
#11ACCEPTED0.02 s4, 5details
#120.27 s4, 5details
#130.71 s4, 5details
#140.71 s4, 5details
#15--2, 5details
#16--3, 5details
#17ACCEPTED0.10 s5details
#18--5details
#19--5details
#20--5details
#21--5details
#22--5details

Compiler report

input/code.cpp: In function 'ANS solve(const Viii&)':
input/code.cpp:347:57: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  347 |             if (R_OCC[R].size() == 1 && L_OCC[R].size() == nnn) {
      |                                         ~~~~~~~~~~~~~~~~^~~~~~
input/code.cpp:460:25: warning: comparison of integer expressions of different signedness: 'std::multiset<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  460 |         if (NOPS.size() == oldsz) return {};
      |             ~~~~~~~~~~~~^~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
using Viii = vector<iii>;
using ANS = optional<Viii>;

#define LEFT get<0>
#define RIGHT get<1>
#define ID get<2>
#define FAKE_ID_BEGIN (-1)
#define FAKE_ID_END (-2)

#define RL(x) ii((x).second, (x).first)

struct TEST {
    Viii V;
    multiset<iii> nops;
    Viii X;
};

Viii compressL(const Viii& V) {
    set<int> RR;
    for (auto [L,R,id] : V) {
        RR.insert(R);
    }
    map<int,int> newL;
    {
        int misses = 0;
        for (auto [L,R_,id_] : V) {
            auto it = RR.lower_bound(L);
            if (it==RR.end() || (*it>L && it==RR.begin())) {
                if (misses++) return {};
                newL[L] = 0;
                continue;
            }
            if (*it > L) --it;
            assert(*it <= L);
            newL[L] = *it;
        }
    }
    Viii X;
    for (auto [L,R,id] : V) {
        X.emplace_back(newL[L], R, id);
    }
    return X;
}

Viii compressR(const Viii& V) {
    set<int> LL;
    for (auto [L,R,id] : V) {
        LL.insert(L);
    }
    map<int,int> newR;
    {
        int misses = 0;
        for (auto [L_,R,id_] : V) {
            auto it = LL.lower_bound(R);
            if (it==LL.end()) {
                if (misses++) return {};
                newR[R] = 1e9+1;
                continue;
            }
            assert(*it >= R);
            newR[R] = *it;
        }
    }
    Viii X;
    for (auto [L,R,id] : V) {
        X.emplace_back(L, newR[R], id);
    }
    return X;
}

Viii remove_nops(TEST& T, const Viii& V) {
    Viii X;
    for (auto [L,R,id] : V) {
        if (id >= 0 && L == R) {
            T.nops.insert(V[id]);
            continue;
        }
        X.emplace_back(L, R, id);
    }
    return X;
}

Viii compress_coord(const Viii& V) {
    set<int> S;
    for (auto [L,R,id] : V) {
        S.insert(L);
        S.insert(R);
    }
    map<int,int> M;
    int next = 0;
    for (int x : S) M[x] = next++;
    Viii X;
    for (auto [L,R,id] : V) {
        X.emplace_back(M[L], M[R], id);
    }
    return X;
}

bool compress(TEST& T) {
    Viii V2 = compressL(T.V);
    if (V2.empty()) return false;
    Viii V3 = compressR(V2);
    if (V3.empty()) return false;
    Viii V4 = remove_nops(T, V3);
    Viii V5 = compress_coord(V4);
    Viii V6 = compressL(V5);
    Viii V7 = compressR(V6);
    T.X = move(V7);
    return true;
}

TEST preprocess(const Viii& V0) {
    TEST T;
    Viii& V = T.V;
    V = V0;
    V.emplace_back(0, 0, FAKE_ID_BEGIN);
    V.emplace_back(1e9+1, 1e9+1, FAKE_ID_END);
    if (!compress(T)) {
        T.V.clear();
    }
    return T;
}

ANS postprocess(TEST& T, const ANS& ans) {
    if (!ans) return {};
    Viii res;
    assert(ID(*ans->begin()) == FAKE_ID_BEGIN);
    assert(ID(*ans->rbegin()) == FAKE_ID_END);
    const Viii& V = T.V;
    multiset<iii> &nops = T.nops;
    for (int i=1; i<(int)ans->size(); i++) {
        int prev_id = ID((*ans)[i-1]);
        int id = ID((*ans)[i]);
        int PREV = prev_id == FAKE_ID_BEGIN ? 0 : RIGHT(V[prev_id]);
        int NEXT = id == FAKE_ID_END ? 1e9 : LEFT(V[id]);
        for (auto it = nops.begin(); it != nops.end();) {
            int L = LEFT(*it);
            int R = RIGHT(*it);
            if (L >= PREV && R <= NEXT) {
                res.push_back(T.V[ID(*it)]);
                PREV = RIGHT(*it);
                it = nops.erase(it);
            }
            else {
                it++;
            }
        }
        if (id >= 0) res.push_back(V[id]);
    }
    if (!nops.empty()) return {};
    return res;
}

bool ok(const multiset<int>& LS, const multiset<int>& RS) {
    set<int> S;
    for (int x:LS) S.insert(x);
    for (int x:RS) S.insert(x);
    int L_below = 0;
    int R_below = 0;
    auto Lit = LS.begin();
    auto Rit = RS.begin();
    for (int x : S) {
        for (; Lit != LS.end() && *Lit <= x; Lit++, L_below++);
        for (; Rit != RS.end() && *Rit <= x; Rit++, R_below++);
        if (L_below > R_below) return false;
        int L_above = LS.size() - L_below;
        int R_above = RS.size() - R_below;
        if (R_above > L_above) return false;
    }
    return true;
}

ANS solve(const Viii& V) {
    if (V.empty()) return {};
    map<int,iii> VM;
    for (auto x : V) VM[ID(x)] = x;
    int n = V.size();
    map<int,int> Lid, Rid;
    map<ii,set<ii>> Ladj, Radj;
    map<int,int> Lmost, Rmost;

    map<ii,int> ALIVE;
    map<ii,vector<int>> BACKLOG;

    multiset<iii> NOPS;
    map<int,set<int>> L_OCC, R_OCC;

    auto hasL = [&](int id) { return Lid.count(id); };
    auto hasR = [&](int id) { return Rid.count(id); };

    std::function<int(int)> get_Lmost;
    get_Lmost = [&](int id) {
        if (!hasL(id)) return id;
        if (!Lmost.count(id)) Lmost[id] = Lid[id];
        return Lmost[id] = get_Lmost(Lmost[id]);
    };
    std::function<int(int)> get_Rmost;
    get_Rmost = [&](int id) {
        if (!hasR(id)) return id;
        if (!Rmost.count(id)) Rmost[id] = Rid[id];
        return Rmost[id] = get_Rmost(Rmost[id]);
    };

    auto kill = [&](int L, int R) {
        ii LR(L,R);
        int id = ALIVE[LR];
        R_OCC[R].erase(id);
        L_OCC[L].erase(id);
        if (!BACKLOG.count(LR)) {
            ALIVE.erase(LR);
            Ladj.erase(LR);
            Radj.erase(LR);
            for (auto& p : Ladj) p.second.erase(RL(LR));
            for (auto& p : Radj) p.second.erase(LR);
        }
        else {
            assert(!BACKLOG[LR].empty());
            int id2 = BACKLOG[LR].back();
            BACKLOG[LR].pop_back();
            ALIVE[LR] = id2;
            if (BACKLOG[LR].empty()) {
                BACKLOG.erase(LR);
            }
        }
    };

    auto is_fixed_begin = [&](int id) { return get_Lmost(id) == FAKE_ID_BEGIN; };
    auto is_fixed_end = [&](int id) { return get_Rmost(id) == FAKE_ID_END; };

    int TODO = n - 1;
    auto spawn = [&](int L, int R, int id) {
        if (L == R && id>=0) {
            id = get_Lmost(id);
            NOPS.emplace(L,R,id);
            TODO--;
            return;
        }
        if (!is_fixed_begin(id)) L_OCC[L].insert(id);
        if (!is_fixed_end(id)) R_OCC[R].insert(id);
        ii LR(L,R);
        if (ALIVE.count(LR)) {
            BACKLOG[LR].push_back(id);
            return;
        }
        for (auto [LR2,id2] : ALIVE) {
            auto [L2,R2] = LR2;
            if (L >= R2) {
                Ladj[LR].insert(RL(LR2));
                Radj[LR2].insert(LR);
            }
            if (L2 >= R) {
                Ladj[LR2].insert(RL(LR));
                Radj[LR].insert(LR2);
            }
        }
        ALIVE[LR] = id;
    };

    for (auto [L,R,id] : V) spawn(L,R,id);

    auto getLR = [&](int id) {
        int L = get_Lmost(id);
        int R = get_Rmost(id);
        return ii(LEFT(VM[L]), RIGHT(VM[R]));
    };

    auto join = [&](int L, int R) {
        TODO--;
        L = get_Rmost(L);
        R = get_Lmost(R);
        ii Lii = getLR(L);
        ii Rii = getLR(R);
        R_OCC[Lii.second].erase(L);
        L_OCC[Rii.first].erase(R);
        assert(Ladj[Rii].count(RL(Lii)));
        assert(Radj[Lii].count(Rii));
        assert(!Lid.count(R));
        assert(!Rid.count(L));
        Rid[L] = R;
        Lid[R] = L;
        Rmost[L] = get_Rmost(R);
        Lmost[R] = get_Lmost(L);
        kill(Lii.first, Lii.second);
        kill(Rii.first, Rii.second);
        spawn(Lii.first, Rii.second, L);
        if (is_fixed_begin(L) && TODO>1) {
            ii newLR(Lii.first, Rii.second);
            for (ii LR2 : set<ii>(Radj[newLR])) {
                if (is_fixed_end(ALIVE[LR2])) {
                    Radj[newLR].erase(LR2);
                    Ladj[LR2].erase(RL(newLR));
                }
            }
        }
        if (is_fixed_end(R) && TODO>1) {
            ii newLR(Lii.first, Rii.second);
            for (ii RL2 : set<ii>(Ladj[newLR])) {
                if (is_fixed_begin(ALIVE[RL(RL2)])) {
                    Ladj[newLR].erase(RL2);
                    Radj[RL(RL2)].erase(newLR);
                }
            }
        }
    };
    while (TODO > 0) {
        if (Ladj.empty()) return {};
        if (Radj.empty()) return {};
        if (TODO == 1) {
            assert(ALIVE.size() == 2);
            for (auto [LR,id] : ALIVE) {
                for (auto [LR2,id2] : ALIVE) if (id != id2) {
                    if (LR.second <= LR2.first) {
                        Ladj[LR2].insert(RL(LR));
                        Radj[LR].insert(LR2);
                        join(id, id2);
                        goto next;
                    }
                }
            }
        }
        for (const auto& [LR,S] : Ladj) {
            if (is_fixed_begin(ALIVE[LR])) continue;
            if (S.empty()) return {};
            if (S.size() == 1) {
                ii LR2 = RL(*S.begin());
                join(ALIVE[LR2], ALIVE[LR]);
                goto next;
            }
        }
        for (const auto& [LR,S] : Radj) {
            if (is_fixed_end(ALIVE[LR])) continue;
            if (S.empty()) return {};
            if (S.size() == 1) {
                ii LR2 = *S.begin();
                join(ALIVE[LR], ALIVE[LR2]);
                goto next;
            }
        }
        for (auto [LR,id] : ALIVE) {
            auto [L,R] = LR;
            int nnn = 1 + (L==R);
            if (R_OCC[R].size() == 1 && L_OCC[R].size() == nnn) {
                const auto& S = Radj[LR];
                join(id, ALIVE[*S.begin()]);
                goto next;
            }
        }
        if (0) {
            map<int,int> L_OCC, R_OCC;
            for (auto [LR,id] : ALIVE) {
                auto [L,R] = LR;
                if (!is_fixed_begin(id)) L_OCC[L]++;
                if (!is_fixed_end(id)) R_OCC[R]++;
            }
            for (auto [LR,id] : ALIVE) {
                auto [L,R] = LR;
                int nnn = 1 + (L==R);
                if (R_OCC[R] == 1 && L_OCC[R] == nnn) {
                    const auto& S = Radj[LR];
                    join(id, ALIVE[*S.begin()]);
                    goto next;
                }
            }
        }
        if (0) {
            multiset<int> LS, RS;
            for (auto [L,R,id] : V) {
                if (id != FAKE_ID_BEGIN && !hasL(id)) LS.insert(L);
                if (id != FAKE_ID_END && !hasR(id)) RS.insert(R);
            }
            for (auto [LR,id] : ALIVE) {
                if (is_fixed_begin(id)) continue;
                if (is_fixed_end(id)) continue;
                int first = RIGHT(getLR(FAKE_ID_BEGIN));
                auto [L,R] = LR;
                if (L < first) continue;
                LS.erase(LS.find(L));
                RS.erase(RS.find(first));
                if (!ok(LS,RS)) {
                    LS.insert(L);
                    RS.insert(first);
                    continue;
                }
                join(FAKE_ID_BEGIN, id);
                goto next;
            }
        }
        //return {};
        for (const auto& [LR,S] : Ladj) {
            if (is_fixed_begin(ALIVE[LR])) continue;
            assert(S.size() >= 2);
            auto it = S.rbegin();
            auto it2 = next(it);
            if (it->first != it2->first) {
                join(ALIVE[RL(*it)], ALIVE[LR]);
                goto next;
            }
        }
        for (const auto& [LR,S] : Radj) {
            if (is_fixed_end(ALIVE[LR])) continue;
            assert(S.size() >= 2);
            auto it = S.begin();
            auto it2 = next(it);
            if (it->first != it2->first) {
                join(ALIVE[LR], ALIVE[*it]);
                goto next;
            }
        }
        for (const auto& [LR,S] : Radj) {
            if (is_fixed_end(ALIVE[LR])) continue;
            assert(S.size() >= 2);
            auto it = S.begin();
            if (it->first == LR.second) {
                join(ALIVE[LR], ALIVE[*it]);
                goto next;
            }
        }
        return {};
next:;
    }

    Viii ans;
    for (int id = FAKE_ID_BEGIN;; id = Rid[id]) {
        ans.push_back(VM[id]);
        if (id == FAKE_ID_END) break;
    }
    while (!NOPS.empty()) {
        int oldsz = NOPS.size();
        Viii res;
        res.push_back(ans[0]);
        for (int i=1; i<(int)ans.size(); i++) {
            int prev_id = ID(ans[i-1]);
            int id = ID(ans[i]);
            int PREV = prev_id == FAKE_ID_BEGIN ? 0 : RIGHT(VM[prev_id]);
            int NEXT = id == FAKE_ID_END ? 1e9 : LEFT(VM[id]);
            for (auto it = NOPS.begin(); it != NOPS.end();) {
                int L = LEFT(*it);
                int R = RIGHT(*it);
                if (L >= PREV && R <= NEXT) {
                    int xx = ID(*it);
                    for (;;) {
                        res.push_back(VM[xx]);
                        if (!Rid.count(xx)) break;
                        xx = Rid[xx];
                    }
                    it = NOPS.erase(it);
                }
                else {
                    it++;
                }
            }
            res.push_back(VM[id]);
        }
        swap(ans, res);
        if (NOPS.size() == oldsz) return {};
    }
    return ans;
}

ANS solve2(const Viii& V) {
    TEST T = preprocess(V);
    auto ans = solve(T.X);
    if (ans) {
        return postprocess(T, *ans);
    }
    return {};
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin>>t;
    while (t--) {
        int n; cin>>n;
        set<iii> S;
        vector<iii> V;
        for (int i=0; i<n; i++) {
            int x,y; cin>>x>>y;
            S.emplace(x,y,i);
            V.emplace_back(x,y,i);
        }
        if (n==1) {
            cout << "YES\n";
            cout << LEFT(V[0]) << ' ' << RIGHT(V[0]) << '\n';
            continue;
        }
        if (ANS ans = solve2(V)) {
            cout << "YES\n";
            for (auto [x,y,_] : *ans) {
                cout << x << ' ' << y << '\n';
            }
        }
        else cout << "NO\n";
    }
}

Test details

Test 1

Group: 1, 4, 5

Verdict: ACCEPTED

input
100
1
74 75
1
100 43
...
view save

correct output
YES
74 75
YES
100 43
YES
...
view save

user output
YES
74 75
YES
100 43
YES
...
Truncated

Test 2

Group: 1, 4, 5

Verdict: ACCEPTED

input
100
2
80 54
51 61
2
...
view save

correct output
YES
51 61
80 54
YES
2 64
...
view save

user output
YES
51 61
80 54
YES
2 64
...
Truncated

Test 3

Group: 1, 4, 5

Verdict: ACCEPTED

input
100
3
3 74
91 45
100 24
...
view save

correct output
YES
3 74
100 24
91 45
YES
...
view save

user output
YES
3 74
91 45
100 24
YES
...
Truncated

Test 4

Group: 1, 4, 5

Verdict: ACCEPTED

input
100
4
88 50
62 41
12 86
...
view save

correct output
YES
12 86
88 50
62 41
66 93
...
view save

user output
YES
12 86
88 50
62 41
66 93
...
Truncated

Test 5

Group: 1, 4, 5

Verdict: ACCEPTED

input
100
5
82 80
80 92
5 22
...
view save

correct output
YES
5 22
94 13
82 80
80 92
...
view save

user output
YES
5 22
82 80
80 92
93 91
...
Truncated

Test 6

Group: 1, 2, 4, 5

Verdict: ACCEPTED

input
100
5
34 38
26 30
1 6
...
view save

correct output
YES
1 6
12 22
26 30
34 38
...
view save

user output
YES
1 6
12 22
26 30
34 38
...
Truncated

Test 7

Group: 1, 3, 4, 5

Verdict: ACCEPTED

input
100
5
50 40
28 25
51 7
...
view save

correct output
YES
51 7
50 40
47 1
17 11
...
view save

user output
YES
17 11
28 25
50 40
51 7
...
Truncated

Test 8

Group: 1, 4, 5

Verdict: ACCEPTED

input
100
5
2 2
2 1
1 1
...
view save

correct output
YES
1 2
2 1
2 1
1 1
...
view save

user output
YES
1 1
2 2
2 1
1 2
...
Truncated

Test 9

Group: 2, 4, 5

Verdict: ACCEPTED

input
100
100
175870020 296379324
248160539 883842002
21934885 781732852
...
view save

correct output
NO
YES
4976156 6890135
10553287 11923223
14617057 17728163
...
view save

user output
NO
YES
4976156 6890135
10553287 11923223
14617057 17728163
...
Truncated

Test 10

Group: 3, 4, 5

Verdict:

input
100
100
447597377 314433951
700232436 691277009
937268439 708165426
...
view save

correct output
YES
998963839 391778929
995772196 257222033
995754704 553123757
994629465 247775824
...
view save

user output
NO
NO
NO
NO
NO
...
Truncated

Test 11

Group: 4, 5

Verdict: ACCEPTED

input
100
100
1 1
1 2
2 1
...
view save

correct output
YES
1 2
2 1
1 2
2 2
...
view save

user output
YES
1 1
1 1
1 1
1 1
...
Truncated

Test 12

Group: 4, 5

Verdict:

input
100
100
7 1
6 3
10 9
...
view save

correct output
YES
6 7
7 8
9 10
10 10
...
view save

user output
YES
1 9
9 9
9 9
9 2
...
Truncated

Test 13

Group: 4, 5

Verdict:

input
100
100
51 5
85 77
91 84
...
view save

correct output
YES
100 24
100 25
100 3
100 6
...
view save

user output
NO
NO
NO
YES
13 6
...
Truncated

Test 14

Group: 4, 5

Verdict:

input
100
100
823828194 863717310
593641073 340054211
420481158 965069109
...
view save

correct output
YES
999289319 634855378
996775156 433726648
983657502 55234695
981890636 112877413
...
view save

user output
NO
NO
NO
NO
NO
...
Truncated

Test 15

Group: 2, 5

Verdict:

input
100
500
88724450 89315226
266915464 267648621
189301651 189661541
...
view save

correct output
YES
764920 1459946
1936195 2832987
3691481 4085931
4991808 5840928
...
view save

user output
(empty)

Test 16

Group: 3, 5

Verdict:

input
100
500
763682761 317584504
756010800 260162861
435911339 78070399
...
view save

correct output
YES
998768285 3307355
998714926 628486754
997115613 820932481
993320616 554600893
...
view save

user output
(empty)

Test 17

Group: 5

Verdict: ACCEPTED

input
100
500
2 2
2 1
1 2
...
view save

correct output
YES
1 2
2 2
2 1
1 2
...
view save

user output
YES
1 1
1 1
1 1
1 1
...
Truncated

Test 18

Group: 5

Verdict:

input
100
500
10 6
10 10
9 10
...
view save

correct output
YES
2 3
3 4
4 5
5 6
...
view save

user output
(empty)

Test 19

Group: 5

Verdict:

input
100
500
85 87
89 70
70 92
...
view save

correct output
YES
96 97
100 67
100 10
100 97
...
view save

user output
(empty)

Test 20

Group: 5

Verdict:

input
100
500
861154169 119512584
569086662 606567153
288230434 322196278
...
view save

correct output
YES
999945324 969534372
999738857 240617694
999244114 722161553
999207839 557351400
...
view save

user output
(empty)

Test 21

Group: 5

Verdict:

input
100
500
116439250 401518028
280329609 193466222
674040956 209050570
...
view save

correct output
NO
YES
773701149 773852119
987509190 315670966
977413249 510418200
...
view save

user output
(empty)

Test 22

Group: 5

Verdict:

input
100
500
934181189 942499518
684836806 395802802
957884803 570946201
...
view save

correct output
YES
999772640 505132174
999111650 140844643
999028633 888134186
999020109 291046771
...
view save

user output
(empty)

Tasks

A Vuodet-B Arvonta-C Kolmijako-D Järjestys-

Submissions (jlaire)

2025-09-07 02:01:43 102025-09-07 02:00:33 102025-09-07 00:17:42 302025-09-07 00:14:00 202025-09-07 00:08:02 102025-09-05 19:25:08 102025-09-05 19:24:25 02025-09-05 19:06:41 10