제출 #604654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604654		Sam_a17	버섯 세기 (IOI20_mushrooms)	C++14	0 / 100	17 ms	1456 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(x) cout << #x << " " << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin());
 
#define pb push_back
#define ld long double
#define ll long long
 
// #include "mushrooms.h"
int use_machine(vector<int> m);
 
void pr(vector<int>& a) {
  cerr << "arr" << " ";
  for(auto i: a) {
    cerr << i << " "; 
  } cerr << endl;
}

int count_mushrooms(int n) {
	// std::vector<int> m;
	// for (int i = 0; i < n; i++)
		// m.push_back(i);
	// int c1 = use_machine(m);
	// m = {0, 1};
	// int c2 = use_machine(m);
	// return c1+c2;
 
  // int curr = 1;
  // vector<int> a{0}, b;
  // int s = 1;
  // for(int i = 1; i + 1 < n; i += 2) {
  //   vector<int> ask{i, 0, i + 1};
  //   int c1 = use_machine(ask);
  //   s += 2 - c1;
  // }
 
  // if(n % 2 == 0) {
  //   vector<int> ask{0, n - 1};
  //   int c1 = use_machine(ask);
  //   s += 1 - c1;
  // }

  set<int> st;
  for(int i = 0; i < n; i++) {
    st.insert(i);
  }

  int answ = 0;
  int kx = 30, cx = 0, cnt = 0, qn = 0;
  vector<int> ones;
  for(int i = 0; i < n; i++) {
    int ina = i + 1, inb = n - 1, ans = i;
    while(ina <= inb) {
      int mid = (ina + inb) / 2;
      vector<int> aski;
      for(int j = i; j <= mid; j++) {
        aski.push_back(j);
      }

      if(use_machine(aski) == 0) {
        ina = mid + 1;
        ans = mid;
      } else {
        inb = mid - 1;
      }
      qn++;
    }

    int si = ans - i + 1;
    if(cnt % 2 == 0) {
      kx -= si;
      cx += si;
    
      for(int j = i; j <= ans; j++) {
        st.erase(j);
        ones.push_back(j);
      } 
    }

    if(kx < 0) {
      break;
    }
    // dbg(ans)
    cnt++;
    i = ans;
  }

  // dbg(qn)
  // dbg(kx)
  // dbg(cx)

  vector<int> mnac;
  for(auto i: st) {
    mnac.push_back(i);
  }

  int i = 0;
  for(; i + cx <= sz(mnac); i += cx) {
    vector<int> qry;
    for(int j = i, k = 0; j < i + cx; j++, k++) {
      qry.push_back(ones[k]);
      qry.push_back(mnac[j]);
    }

    // pr(qry);
    int s = use_machine(qry);

    int ci = 0;
    if(s % 2 == 1) {
      s--, ci++;
    } 
    answ += (cx - ci) - (s / 2);
  }

  vector<int> qry;
  int ki = 0;
  for(int j = i; j < sz(mnac); j++, ki++) {
    qry.push_back(mnac[j]);
    qry.push_back(ones[ki]);
  }
  // dbg(answ)
  if(!qry.empty()) {
    // pr(qry);
    int s = use_machine(qry), ci = 0;
    if(s % 2 == 1) {
      s--, ci++;
    } 
    answ += (sz(qry) / 2 - ci) - (s / 2);
    // dbg(answ)
  }
  return answ + cx;
}

• Subtask 1: 0 / 100