제출 #604687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604687		Sam_a17	버섯 세기 (IOI20_mushrooms)	C++14	10 / 100	157 ms	1280 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 kAx = 1, kBx = 0, cnt = 0, qn = 0;
  vector<int> ones, zeroes{0};
  int start = -1;
  for(int i = 1; i < n; i++) {
    vector<int> aski{0, i};
    int s = use_machine(aski);
    if(s == 1) {
      ones.push_back(i);
      kBx++;
    } else {
      zeroes.push_back(i);
      kAx++;
    }

    if(kAx >= 2 || kBx >= 2) {
      start = i + 1;
      break;
    }
  }

  if(start == -1) {
    return kAx;
  }

  // dbg(kAx)
  // dbg(kBx)

  if(kAx >= 60 || !kBx) {
    int i = start;
    for(; i + kAx <= n; i += kAx) {
      vector<int> qry;
      for(int j = i, k = 0; j < i + kAx; j++, k++) {
        qry.push_back(zeroes[k]);
        qry.push_back(j);
      }

      int s = use_machine(qry);

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

    vector<int> qry;
    int ki = 0;
    for(int j = i; j < n; j++, ki++) {
      qry.push_back(zeroes[ki]);
      qry.push_back(j);
    }

    if(!qry.empty()) {
      int s = use_machine(qry), ci = 0;
      if(s % 2 == 1) {
        s--, ci++;
      } 
      answ += (sz(qry) / 2 - ci) - (s / 2);
    }
    return answ + kAx;
  } else {
    int i = start;
    for(; i + kBx <= n; i += kBx) {
      vector<int> qry;
      for(int j = i, k = 0; j < i + kBx; j++, k++) {
        qry.push_back(ones[k]);
        qry.push_back(j);
      }

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

      if(s % 2 == 1) {
        s--, answ++;
      }
      answ += (s / 2);
      // dbg(answ)
    }

    vector<int> qry;
    int ki = 0;
    for(int j = i; j < n; j++, ki++) {
      qry.push_back(ones[ki]);
      qry.push_back(j);
    }


    if(!qry.empty()) {
      int s = use_machine(qry);
      if(s % 2 == 1) {
        s--, answ++;
      }
      answ += (s / 2);
    }
    return answ + kAx;
  }
}

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

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:55:25: warning: unused variable 'cnt' [-Wunused-variable]
   55 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                         ^~~
mushrooms.cpp:55:34: warning: unused variable 'qn' [-Wunused-variable]
   55 |   int kAx = 1, kBx = 0, cnt = 0, qn = 0;
      |                                  ^~

• Subtask 1: 10 / 100