oj.uz

답안 #838469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838469 2023-08-27T07:09:51 Z Trumling 드문 곤충 (IOI22_insects) C++17
0 / 100
 1 ms 336 KB 
#include "insects.h"
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

struct Trum
{
  int l,r;
  vector<int> here;

};
int min_cardinality(int N) 
{
ll n=N;
vector<int>type(n,-1);
vector<int>count(n,1);
vector<int>v;
set<int>s;
  for(int i=0;i<N;i++)
    {
      move_inside(i);
      ll p=press_button();
      if(p!=1)
      move_outside(i);
      else
      {
       type[i]=i;
       s.insert(i);
       v.pb(i);
      }
    }
  Trum curr;
  for(int i=0;i<N;i++)
  if(type[i]==-1)
  curr.here.pb(i);

  
  queue<Trum>q;
  
  curr.l=0;
  curr.r=v.size()-1;

  q.push(curr);

  while(!q.empty())
  {
    curr=q.front();
    q.pop();

    if(curr.l==curr.r)
    {
      count[v[curr.l]]+=curr.here.size();
      continue;
    }

    if(!curr.here.size())
    continue;

    ll mid=(curr.l+curr.r)/2;

    for(int i=curr.l;i<=curr.r;i++)
    {
      if(i<=mid && s.find(v[i])==s.end())
      {
        move_inside(v[i]);
        s.insert(v[i]);
      }

      if(i>mid && s.find(v[i])!=s.end())
      {
        move_outside(v[i]);
        s.erase(v[i]);
      }
    }
    Trum l,r;
    l.l=curr.l;
    l.r=mid;

    r.l=mid+1;
    r.r=curr.r;
    for(auto x:curr.here)
    {
      move_inside(x);
      ll p=press_button();
      if(p!=1)
      l.here.pb(x);
      else
      r.here.pb(x);

      move_outside(x);
    }

    q.push(l);
    q.push(r);
    
  }


}

Compilation message

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:107:1: warning: no return statement in function returning non-void [-Wreturn-type]
  107 | }
      | ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -