제출 #628798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628798		toloraia	드문 곤충 (IOI22_insects)	C++17	47.51 / 100	229 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

int A (int n, vector < int > V){
    vector < bool > fix (n, 1);
    for (int x : V)
        fix[x] = 0;
    srand (time (0));
    random_shuffle(V.begin(), V.end());
    int m = (int)V.size();
    vector < int > L(n, 0);
    vector < int > R(n, m-1);
    vector < int > M(n);
    for (int I = 0; (1 << I) < m*2; I++){
        vector < int > v[m];
        bool ok = 1;
        for (int i = 0; i < n; i++){
            if (fix[i] == 0)
                continue;
            if (L[i] == R[i])
                continue;
            ok = 0;
            M[i] = (L[i] + R[i] >> 1);
            v[M[i]].push_back (i);
        }
        if (ok)
            break;
        for (int i = 0; i < m; i++){
            move_inside(V[i]);
            for (int x : v[i]){
                move_inside(x);
                if (press_button() == 1)
                    L[x] = M[x] + 1;
                else
                    R[x] = M[x];
                move_outside(x);
            }
        }
        for (int x : V)
            move_outside(x);
    }
    vector < int > cnt (m, 1);
    for (int i = 0; i < n; i++)
        if (fix[i])
            cnt[L[i]]++;
    int ans = cnt[0];
    for (int i = 1; i < m; i++)
        ans = min (ans, cnt[i]);
    return ans;
}

int B (int n, vector < int > V){
    vector < bool > fix (n, 1);
    for (int x : V)
        fix[x] = 0;
    int ans = 1;
    int m = (int)V.size();
    while (1){
        V.clear();
        for (int i = 0; i < n; i++)
            if (fix[i])
                V.push_back(i);
        if ((int)V.size() < m)
            return ans;
        vector < int > v;
        for (int x : V){
            move_inside(x);
            if (press_button() == 1){
                v.push_back(x);
                fix[x] = 0;
            }
            else
                move_outside(x);
        }
        for (int x : v)
            move_outside(x);
        if ((int)v.size() < m)
            return ans;
        ans++;
    }
    return ans;
}

int C (int n, int m, vector < int > V){
    vector < bool > fix (n, 1);
    for (int x : V)
        fix[x] = 0;
    V.clear();
    for (int i = 0; i < n; i++)
        if (fix[i])
            V.push_back (i);
    int l = 1, r = n/m;
    //cout << l << " " << r << endl;
    while (l < r){
        int mid = l + r + 1 >> 1;
        vector < int > v;
        for (int i : V){
            move_inside(i);
            if (press_button() < mid){
                v.push_back(i);
            }
            else
                move_outside(i);
        }
        for (int x : v)
            move_outside(x);
        if ((int)v.size() == m*(mid-1))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

int min_cardinality(int n) {
    vector < int > V;
    for (int i = 0; i < n; i++){
        move_inside(i);
        if (press_button() == 1)
            V.push_back(i);
        else
            move_outside(i);
    }
    for (int x : V)
        move_outside(x);
    int m = (int)V.size();
    int k = n - m;
    int ans1 = 0;
    while ((1 << ans1) < m)
        ans1++;
    ans1 *= n;
    int ans2 = 0;
    while ((1 << ans2) < n/m)
        ans2++;
    ans2 *= n-m;
    //cout << ans1 << " " << ans2 << endl;
    //if (ans1 < ans2)
      //  return A(n, V);

    return C(n, m, V);
}

컴파일 시 표준 에러 (stderr) 메시지

insects.cpp: In function 'int A(int, std::vector<int>)':
insects.cpp:24:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |             M[i] = (L[i] + R[i] >> 1);
insects.cpp: In function 'int C(int, int, std::vector<int>)':
insects.cpp:96:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         int mid = l + r + 1 >> 1;
      |                   ~~~~~~^~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:128:9: warning: unused variable 'k' [-Wunused-variable]
  128 |     int k = n - m;
      |         ^

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 22.51 / 75