oj.uz

Submission #926865

# Submission time Handle Problem Language Result Execution time Memory
926865 2024-02-14T01:18:26 Z beaboss Rarest Insects (IOI22_insects) C++17
0 / 100
 2000 ms 600 KB 
// Source: https://oj.uz/problem/view/IOI22_insects
// 
#include "insects.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

set<int> in, out;

void gout(int i) {
  in.erase(i);
  out.insert(i);
  move_outside(i);
}

void gin(int i) {
  out.erase(i);
  in.insert(i);
  move_inside(i);
}

int min_cardinality(int n) {

  // cout << n << endl;
  FOR(i, 0, n) out.insert(i);

  int d = n;
  FOR(i, 0, n) {
    gin(i);
    if (press_button() > 1) {
      gout(i);
      d--;
    }
  }

  set<int> oth = in;
  for (auto val: oth) {
    gout(val);

  }

  if (d == 1) {
    return n;
  }

  int alr = 0;
  // cout << 'd' << endl;
  int prv = -1;
  int lo  = 1;
  int hi = n / 2;
  // int alr = 0;
  while (lo < hi) {
    int t = (lo + hi + d - 1) / (d);
    // cout << out.size() << t << endl;
    // for (auto val: out) {
    //   cout << val << ' ';
    // }
    // cout << endl;
    // testing t
    // cout << lo << hi << t << endl;
    set<int> oth = out;
    for (auto val: oth) {
      gin(val);
      if (press_button() > t) {
        gout(val);
      }
    }
    // cout << in.size() << endl;
    if (in.size() + alr == t * d) { // all here --- erase this section
      // alr += t;
      // for (auto it = in.begin(); it != in.end();) {
      //   move_outside(*it);
      //   it++;
      //   in.erase(prev(it, 1));
      // }
      // set<int> oth = in;
      // for (auto val: oth) gout(val);
      alr += in.size();
      in.clear();
      lo = t;
    } else { // erase everything not in this section
      out.clear();
      set<int> oth = in;
      for (auto val: oth) gout(val);
      hi = t-1;
    }

  }
  // cout << alr << endl;

  return lo;

}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:86:25: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |     if (in.size() + alr == t * d) { // all here --- erase this section
      |         ~~~~~~~~~~~~~~~~^~~~~~~~
insects.cpp:65:7: warning: unused variable 'prv' [-Wunused-variable]
   65 |   int prv = -1;
      |       ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Execution timed out 3083 ms 600 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Execution timed out 3083 ms 600 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 9 ms 344 KB Output is correct
8 Execution timed out 3086 ms 600 KB Time limit exceeded
9 Halted 0 ms 0 KB -