oj.uz

Submission #1058119

# Submission time Handle Problem Language Result Execution time Memory
1058119 2024-08-14T08:34:52 Z hirayuu_oj Rarest Insects (IOI22_insects) C++17
0 / 100
 72 ms 848 KB 
#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

int min_cardinality(int N) {
    vector<int> types;
    vector<bool> mark(N,false);
    rep(i,N) {
        move_inside(i);
        if(press_button()==1) {
            mark[i]=true;
            types.emplace_back(i);
        }
        else move_outside(i);
    }
    if(types.size()==1)return N;
    vector<int> cnt(types.size(),1);
    vector<vector<array<int,3>>> ser(types.size()+1);
    rep(i,N) {
        if(!mark[i])ser[types.size()/2].push_back({i,(int)types.size(),0});
    }
    int rest=N-types.size();
    int pos=types.size();
    while(rest) {
        for(auto data:ser[pos]) {
            int mid=pos;
            int ok=data[1];
            int ng=data[2];
            move_inside(data[0]);
            if(press_button()==2) {
                ok=mid;
            }
            else {
                ng=mid;
            }
            move_outside(data[0]);
            if(abs(ok-ng)==1) {
                cnt[ok-1]++;
                rest--;
            }
            else {
                ser[(ok+ng)/2].push_back({data[0],ok,ng});
            }
        }
        ser[pos].clear();
        pair<int,int> near={998244353,-1};
        rep(i,types.size()+1) {
            if(ser[i].size())near=min(near,{abs(pos-i),i});
        }
        if(near.second<pos) {
            pos--;
            move_outside(pos);
        }
        else {
            move_inside(pos);
            pos++;
        }
    }
    int ans=998244353;
    for(int i:cnt)ans=min(ans,i);
    return ans;
}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,n) for(int i=0; i<(n); i++)
      |                                ^
insects.cpp:51:9: note: in expansion of macro 'rep'
   51 |         rep(i,types.size()+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 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 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Incorrect 5 ms 444 KB Wrong answer.
9 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 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 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Incorrect 5 ms 444 KB Wrong answer.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 75.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 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 7 ms 344 KB Output is correct
8 Correct 11 ms 600 KB Output is correct
9 Incorrect 72 ms 848 KB Wrong answer.
10 Halted 0 ms 0 KB -