제출 #804563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
804563		Ronin13	드문 곤충 (IOI22_insects)	C++17	47.50 / 100	133 ms	456 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back 
using namespace std;

int min_cardinality(int n) {
  vector <int> act;
  bool used[n + 1];
  fill(used, used + n + 1, false);
  for(int i = 0; i < n; i++){
    move_inside(i);
    int x = press_button();
    if(x == 2) move_outside(i), used[i] = true;
    else act.pb(i);
  }
  //for(int to : act) cout << to << ' ';
  //int l = 0, r = act.size();
  for(int to : act) move_outside(to);
  int L[n], R[n];
  for(int i = 0; i < n; i++){
    if(used[i]) L[i] = -1, R[i] =act.size()- 1;
  }
  for(int j = 0; j < 11; j++){
    vector <vector <int> > vv(act.size());
    for(int i = 0; i < n; i++){
      if(L[i] - R[i] == -1) continue;
      if(!used[i]) continue;
      int mid = L[i] + R[i];
      
      mid /= 2;
     // cout << mid << "\n";
      vv[mid].pb(i);
    }
    
    
    for(int i= 0; i < act.size(); i++){
      move_inside(act[i]);
      for(int to : vv[i]){
        move_inside(to);
        int x = press_button();
        if(x == 2) R[to] = i;
        else L[to] = i;
        move_outside(to);
      }
      
    }
    for(int to : act) move_outside(to);
  }
  int cnt[n + 1];
  fill(cnt, cnt + n + 1, 1e9);
  
  for(int j = 0; j < act.size(); j++){
    cnt[j] = 1;
  }
  for(int i = 0; i < n; i++){
    if(used[i]) cnt[R[i]]++;
  }
  int mn = 1e9;
  for(int i = 0; i < act.size(); i++){
      mn = min(mn, cnt[i]);
  }
  return mn;
  return 0;
}

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

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i= 0; i < act.size(); i++){
      |                   ~~^~~~~~~~~~~~
insects.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int j = 0; j < act.size(); j++){
      |                  ~~^~~~~~~~~~~~
insects.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i = 0; i < act.size(); i++){
      |                  ~~^~~~~~~~~~~~

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