— 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:ArktinenKarpalo
Submission time:2025-09-27 00:32:57 +0300
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.37 s1, 2, 3details
#20.37 s1, 2, 3details
#30.37 s1, 2, 3details
#40.37 s1, 2, 3details
#50.37 s1, 2, 3details
#60.37 s2details
#70.37 s2details
#80.37 s2details
#90.37 s2, 3details
#100.37 s3details
#110.37 s3details
#120.37 s3details
#130.37 s3details
#140.37 s3details
#150.37 s3details
#160.37 s3details

Compiler report

input/code.cpp: In function 'int cnt_fst(std::bitset<100000>&, int)':
input/code.cpp:12:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   for (int i = 0; i < bs.size(); i) {
      |                   ~~^~~~~~~~~~~
input/code.cpp:12:34: warning: for increment expression has no effect [-Wunused-value]
   12 |   for (int i = 0; i < bs.size(); i) {
      |                                  ^
input/code.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::size_t' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if (i + Y < bs.size()) {
      |         ~~~~~~^~~~~~~~~~~

Code

#include <bits/stdc++.h>

#define N 100000

using namespace std;

#define Y 512

int cnt_Y(const std::bitset<Y> &lol) { return lol.count(); }
int cnt_fst(bitset<100000> &bs, int n) {
  int cnt = 0;
  for (int i = 0; i < bs.size(); i) {
    if (i + Y < bs.size()) {
      int cnt2 = cnt_Y(*(((bitset<Y> *)((void *)(&bs)) + (i / 8))));
      if (cnt2 + cnt < n) {
        i += Y;
        cnt += cnt2;
				continue;
        // return i;
      }
    }
    if (bs[i])
      cnt++;
    if (cnt == n)
      return i;
    i++;
  }
  return -1;
}

void bsprint(bitset<100000> &bs) {
  for (int i = 0; i < 10; i++) {
    cout << bs[i];
  }
  cout << endl;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, t;
  cin >> n >> t;
  vector<int> a(n), b(n);
  vector<pair<int, int>> childrenA;
  vector<pair<int, int>> childrenB;
  array<bitset<100000>, 100001> A, B;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    childrenA.push_back({a[i], i});
    childrenB.push_back({b[i], i});
  }
  sort(childrenA.begin(), childrenA.end());
  bitset<100000> bs;
  auto it = childrenA.begin();
  for (int i = 1; i <= n; i++) {
    while (it != childrenA.end() && it->first == i) {
      bs.set(it->second);
      it++;
    }
    A[i] = bs;
  }
  bs.set();
  sort(childrenB.begin(), childrenB.end());
  it = childrenB.begin();
  for (int i = 1; i <= n; i++) {
    while (it != childrenA.end() && it->first == i - 1) {
      bs.reset(it->second);
      it++;
    }
    B[i] = bs;
  }
  while (t--) {
    int m;
    cin >> m;
    bitset<100000> C;
    C.set();
    C >>= (100000 - n);
    vector<int> k(m);
    for (int i = 0; i < m; i++)
      cin >> k[i];
    sort(k.begin(), k.end());
    bool ok = true;
    for (int i = 0; i < m; i++) {
      int cr = k[i];
      auto candidates = A[cr] & B[cr] & C;
      int until = cnt_fst(candidates, cr);
      if (until == -1) {
        ok = false;
        break;
      }
      candidates <<= (100000 - until - 1);
      candidates >>= (100000 - until - 1);
      C ^= candidates;
    }

    if (ok) {
      cout << "YES\n";
    } else {
      cout << "NO\n";
    }
  }
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

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

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

user output
(empty)

Test 2

Group: 1, 2, 3

Verdict:

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

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

user output
(empty)

Test 3

Group: 1, 2, 3

Verdict:

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

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

user output
(empty)

Test 4

Group: 1, 2, 3

Verdict:

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

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

user output
(empty)

Test 5

Group: 1, 2, 3

Verdict:

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

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

user output
(empty)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

Tasks

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

Submissions (ArktinenKarpalo)

2025-09-27 01:47:57 1002025-09-27 01:46:58 102025-09-27 01:46:23 102025-09-27 01:43:41 852025-09-27 01:43:27 852025-09-27 01:43:11 852025-09-27 01:42:50 102025-09-27 01:42:20 852025-09-27 01:42:07 852025-09-27 01:42:01 102025-09-27 01:41:12 102025-09-27 01:39:36 102025-09-27 01:39:21 102025-09-27 01:38:31 02025-09-27 01:29:18 02025-09-27 01:28:30 02025-09-27 01:19:49 02025-09-27 00:34:05 02025-09-27 00:33:13 02025-09-27 00:32:57 02025-09-27 00:31:43 02025-09-27 00:31:19 02025-09-27 00:29:57 02025-09-26 19:58:28 252025-09-26 19:54:53 0