답안 #303490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
303490 2020-09-20T11:07:58 Z rama_pang 버섯 세기 (IOI20_mushrooms) C++14
0 / 100
13 ms 1280 KB
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

int count_mushrooms(int n) {
  const auto Solve = [&](int size_limit) {
    int ans = 1;

    set<int> unknown;
    for (int i = 1; i < n; i++) {
      unknown.emplace(i);
    }
    vector<int> A, B;
    A.emplace_back(0);

    while (!unknown.empty() && (int) max(A.size(), B.size()) < size_limit) {
      if (unknown.size() == 1 || max(A.size(), B.size()) == 1) {
        // query A?
        // can identify ?
        int u = *begin(unknown);
        unknown.erase(u);
        if (use_machine({0, u}) == 1) {
          B.emplace_back(u);
        } else {
          A.emplace_back(u);
          ans += 1;
        }
      } else if (unknown.size() < 5 || max(A.size(), B.size()) < 3 || min(A.size(), B.size()) < 1) {
        // query A?A?
        // can identify both ?
        bool swapped = A.size() < 2;
        if (swapped) {
          swap(A, B);
        }

        int u = *begin(unknown);
        unknown.erase(u);
        int v = *begin(unknown);
        unknown.erase(v);

        int q = use_machine({A[0], u, A[1], v});
        if (q == 0) {
          A.emplace_back(u);
          A.emplace_back(v);
          ans += swapped ? 0 : 2;
        } else if (q == 1) {
          A.emplace_back(u);
          B.emplace_back(v);
          ans += 1;
        } else if (q == 2) {
          B.emplace_back(u);
          A.emplace_back(v);
          ans += 1;
        } else if (q == 3) {
          B.emplace_back(u);
          B.emplace_back(v);
          ans += swapped ? 2 : 0;
        }
        if (swapped) {
          swap(A, B);
        }
      } else {
        // query A?A?A?
        // if first and second ? is the same, can uniquely identify them
        // otherwise, query B?BA?A?A?, where the first and second ? is the
        // same as previously, and other 2 is new element
        // can uniquely identify all of them
        int oldA = A.size();
        bool swapped = A.size() < B.size();
        if (swapped) {
          swap(A, B);
        }

        int u = *begin(unknown);
        unknown.erase(u);
        int v = *begin(unknown);
        unknown.erase(v);
        int w = *begin(unknown);
        unknown.erase(w);

        int q = use_machine({A[0], u, A[1], v, A[2], w});
        if (q & 1) {
          q--;
          B.emplace_back(w);
        } else {
          A.emplace_back(w);
        }
        if (q == 0) {
          A.emplace_back(u);
          A.emplace_back(v);
        } else if (q == 4) {
          B.emplace_back(u);
          B.emplace_back(v);
        } else {
          int c = *begin(unknown);
          unknown.erase(c);
          int d = *begin(unknown);
          unknown.erase(d); 
          q = use_machine({B[0], u, B[1], A[0], v, A[1], c, A[2], d}) - 1;
          if (q & 1) {
            B.emplace_back(d);
          } else {
            A.emplace_back(d);
          }
          if (q & 2) {
            B.emplace_back(c);
          } else {
            A.emplace_back(c);
          }
          if (q & 4) {
            A.emplace_back(u);
            B.emplace_back(v);
          } else {
            B.emplace_back(u);
            A.emplace_back(v);
          }
        }
        if (swapped) {
          swap(A, B);
        }
        ans += int(A.size()) - oldA;
      }
    }

    while (!unknown.empty()) {
      bool swapped = A.size() < B.size();
      if (swapped) {
        swap(A, B);
      }
      vector<int> que;
      for (auto i : A) {
        que.emplace_back(i);
        que.emplace_back(*begin(unknown));
        unknown.erase(begin(unknown));
        if (unknown.empty()) {
          break;
        }
      }
      int q = use_machine(que);
      ans += swapped ? ((q + 1) / 2) : (int(que.size()) / 2 - (q + 1) / 2);
      if (q & 1) {
        B.emplace_back(que.back());
      } else {
        A.emplace_back(que.back());
      }
      if (swapped) {
        swap(A, B);
      }
    }
    return ans;
  };
  
  return Solve(100);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 13 ms 1280 KB Output is correct
8 Correct 13 ms 1280 KB Output is correct
9 Incorrect 4 ms 1280 KB Duplicate value 0 in the query array.
10 Halted 0 ms 0 KB -