— Dark mode

Putka Open 2025 – 2/5

Ryhmät

  • Start: 2025-09-26 18:00:00
  • End: 2025-09-28 23:00:00
Submission details
Task:Ryhmät
Sender:Metabolix
Submission time:2025-10-05 19:16:22 +0300
Language:C++ (C++20)
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.00 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#60.02 s2details
#70.03 s2details
#80.08 s2details
#90.00 s2, 3details
#100.07 s3details
#110.08 s3details
#120.07 s3details
#130.04 s3details
#140.07 s3details
#150.09 s3details
#160.08 s3details

Compiler report

input/code.cpp: In member function 'bool mybits::poista(const mybits&, int)':
input/code.cpp:60:59: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   60 |             for (int shl_min = 0, shl_max = slice_size; c > määrä;) {
      |                                                         ~~^~~~~~~
input/code.cpp:64:24: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   64 |                 if (c2 == määrä) {
      |                     ~~~^~~~~~~~
input/code.cpp:68:24: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   68 |                 if (c2 > määrä) {
      |                     ~~~^~~~~~~

Code

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <bitset>

using namespace std;

struct Toive {
    int alku, loppu, indeksi;
};

struct mybits {
    constexpr static int slice_size = 256;
    constexpr static int slice_count = 100001 / slice_size + 1;
    typedef bitset<slice_size> slice_type;

    bitset<slice_count> oletus;
    unordered_map<int, slice_type> data;

    mybits(bool alkuarvo) {
        if (alkuarvo) {
            oletus.set();
        }
    }
    slice_type slice(int idx) const {
        if (data.contains(idx)) {
            return data.at(idx);
        }
        if (oletus[idx]) {
            return slice_type().set();
        }
        return slice_type();
    }
    void put(int idx, const slice_type& value) {
        if (value == slice_type().set() || value.none()) {
            oletus[idx] = value.test(0);
            data.erase(idx);
            return;
        }
        data[idx] = value;
    }
    void set(int i, bool value) {
        int idx = i / 512;
        int bit = i % 512;
        auto a = slice(idx);
        a.set(bit, value);
        put(idx, a);
    }
    bool poista(const mybits& other, int määrä) {
        for (int i = 0; i < slice_count && määrä; i++) {
            auto old = slice(i);
            auto a = old & other.slice(i);
            auto c = a.count();
            for (int shl_min = 0, shl_max = slice_size; c > määrä;) {
                int shl = (shl_min + shl_max) / 2;
                auto a2 = (a << shl) >> shl;
                auto c2 = a2.count();
                if (c2 == määrä) {
                    put(i, old ^ a2);
                    return true;
                }
                if (c2 > määrä) {
                    shl_min = shl;
                } else {
                    shl_max = shl;
                }
            }
            määrä -= c;
            put(i, old ^ a);
        }
        return määrä == 0;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, t;
    cin >> n >> t;
    vector<pair<int, int>> toiveet_loppu_alku(n), toiveet_alku_indeksi(n);
    for (int i = 0; i < n; i++) {
        cin >> toiveet_loppu_alku[i].second >> toiveet_loppu_alku[i].first;
    }
    ranges::sort(toiveet_loppu_alku);
    for (int i = 0; i < n; i++) {
        toiveet_alku_indeksi[i] = {toiveet_loppu_alku[i].second, i};
    }
    ranges::sort(toiveet_alku_indeksi);

    vector<bool> tulokset(t);
    vector<array<int, 3>> vaiheet;

    for (int testi = 0; testi < t; testi++) {
        tulokset[testi] = true;
        int ryhmien_määrä;
        cin >> ryhmien_määrä;
        map<int, int> ryhmät;
        for (int i = 0; i < ryhmien_määrä; i++) {
            int ryhmän_koko;
            cin >> ryhmän_koko;
            ryhmät[ryhmän_koko] += ryhmän_koko;
        }
        for (auto &[koko, lapsimäärä] : ryhmät) {
            vaiheet.push_back({koko, lapsimäärä, testi});
        }
    }
    ranges::sort(vaiheet);

    mybits kaikki_vapaana(true);
    vector<mybits> vapaat(t, kaikki_vapaana);

    auto toive_iter = toiveet_alku_indeksi.begin();
    set<int> toiveet_kesken;
    mybits toiveet_bits(false);
    for (auto &[koko, lapsimäärä, testi] : vaiheet) {
        if (tulokset[testi] == false) {
            continue;
        }
        while (toive_iter != toiveet_alku_indeksi.end() && toive_iter->first <= koko) {
            int indeksi = toive_iter->second;
            toiveet_kesken.insert(indeksi);
            toiveet_bits.set(indeksi, true);
            toive_iter++;
        }
        while (!toiveet_kesken.empty() && toiveet_loppu_alku[*toiveet_kesken.begin()].first < koko) {
            int indeksi = *toiveet_kesken.begin();
            toiveet_kesken.erase(toiveet_kesken.begin());
            toiveet_bits.set(indeksi, false);
        }
        if (!vapaat[testi].poista(toiveet_bits, lapsimäärä)) {
            tulokset[testi] = false;
        }
    }

    for (auto tulos : tulokset) {
        if (tulos) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
YES
YES
YES
NO
YES
...
view save

user output
YES
YES
YES
NO
YES
...
view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
NO
YES
NO
YES
NO
...
view save

user output
NO
YES
NO
YES
NO
...
view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 100
100 100
100 100
100 100
100 100
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
YES
YES
YES
YES
YES
...
view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 100
4 9
3 8
7 9
7 9
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 6

Group: 2

Verdict:

input
1000 1000
9 10
2 5
10 10
5 5
...
view save

correct output
YES
YES
YES
YES
NO
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 359) >= _Nb (which is 256)

Test 7

Group: 2

Verdict:

input
1000 1000
5 7
9 9
3 7
8 10
...
view save

correct output
YES
NO
NO
YES
YES
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 268) >= _Nb (which is 256)

Test 8

Group: 2

Verdict:

input
1000 1000
1 1
1 1
1 1
1 1
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 256) >= _Nb (which is 256)

Test 9

Group: 2, 3

Verdict:

input
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 256) >= _Nb (which is 256)

Test 10

Group: 3

Verdict:

input
100000 1000
774 778
363 852
309 668
261 459
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 387) >= _Nb (which is 256)

Test 11

Group: 3

Verdict:

input
100000 1000
1233 1914
901 3963
1277 4293
1083 1599
...
view save

correct output
NO
NO
YES
NO
NO
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 290) >= _Nb (which is 256)

Test 12

Group: 3

Verdict:

input
100000 1000
1970 8631
4606 5797
6317 8162
8204 8789
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 455) >= _Nb (which is 256)

Test 13

Group: 3

Verdict:

input
100000 1000
1000 1000
1000 1000
1000 1000
1000 1000
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 256) >= _Nb (which is 256)

Test 14

Group: 3

Verdict:

input
100000 100000
1 100000
1 100000
1 100000
1 100000
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 256) >= _Nb (which is 256)

Test 15

Group: 3

Verdict:

input
100000 100000
80971 98445
93046 96043
74840 94035
95931 96609
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 371) >= _Nb (which is 256)

Test 16

Group: 3

Verdict:

input
100000 10000
6481 14350
69129 87600
6217 16462
4387 16625
...
view save

correct output
YES
YES
YES
YES
YES
...
view save

user output
(empty)

Error:
terminate called after throwing an instance of 'std::out_of_range'
  what():  bitset::set: __position (which is 398) >= _Nb (which is 256)

Tasks

A Ruudukko-B Leimasin-C Alkuluvut-D Ryhmät-

Submissions (Metabolix)

2025-10-05 19:53:26 1002025-10-05 19:40:55 252025-10-05 19:33:25 1002025-10-05 19:32:43 02025-10-05 19:31:41 02025-10-05 19:24:08 252025-10-05 19:18:41 252025-10-05 19:18:23 252025-10-05 19:16:50 252025-10-05 19:16:22 102025-10-05 19:14:40 252025-10-05 19:13:45 252025-10-05 18:34:22 252025-10-05 18:32:14 252025-10-05 18:11:50 252025-10-05 17:12:46 252025-10-04 15:51:37 02025-10-04 15:50:14 252025-10-04 15:49:51 2025-10-04 15:14:23 02025-09-28 11:01:33 102025-09-28 10:57:13 102025-09-28 10:54:26 102025-09-28 10:53:48 2025-09-28 10:40:55 02025-09-27 08:59:55 252025-09-27 08:25:10 02025-09-27 08:20:15 02025-09-27 08:19:27 02025-09-27 07:55:27 252025-09-27 00:25:21 252025-09-27 00:21:33 02025-09-27 00:19:35 252025-09-27 00:17:44 252025-09-27 00:17:23 02025-09-27 00:16:29 02025-09-27 00:13:45 252025-09-27 00:11:02 02025-09-26 23:55:05 02025-09-26 23:54:17 02025-09-26 23:27:56 252025-09-26 23:27:09 02025-09-26 23:23:05 102025-09-26 23:17:56 02025-09-26 23:08:08 102025-09-26 23:07:09 10