답안 #304073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
304073	2020-09-21T02:25:22 Z	Fdg	버섯 세기 (IOI20_mushrooms)	C++14	0 / 100	139 ms	1528 KB

mushrooms

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include "mushrooms.h"

using namespace std;

const int VAL = 141;

vector<int> a, b;

map<int, vector<int>> diff;
set<int> found;

void nextPos(const vector<int>& v, int& pos) {
  while (pos < (int) v.size()) {
    if (found.count(v[pos])) {
      ++pos;
    } else break;
  }
}

void process(int x, bool isA) {
  if (found.count(x)) return;
  found.insert(x);

  if (isA) a.push_back(x);
  else b.push_back(x);

  if (diff.count(x))
    for (int val : diff[x]) {
      process(val, !isA);
    }
}

int count_mushrooms(int n) {
  a.clear(); b.clear(); diff.clear(); found.clear();

  srand(time(NULL));
  vector<int> v;
  for (int i = 1; i < n; ++i)
    v.push_back(i);
  // random_shuffle(v.begin(), v.end());

  int ans = 0, pos = 0;

  bool doNextSimple = false;

  a.push_back(0); found.insert(0);
  while (/*a.size() < VAL && b.size() < VAL && */pos < (int) v.size()) {
    if (a.size() > 1) {
      vector<int> arr;
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(v[pos]), ++pos;
        arr.push_back(a[0]);
      }
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(v[pos]), ++pos;
        arr.push_back(a[1]); 
      }
      if (!doNextSimple) {
        nextPos(v, pos);
        if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos;
      }

      doNextSimple = true;
      int ret = use_machine(arr);
      if (arr.size() == 2) {
        if (ret == 1) {
          process(arr[0], false);
        } else {
          process(arr[0], true);
        }
      } else if (arr.size() == 4) {
        if (ret == 3) {
          process(arr[0], false);
          process(arr[2], false);
        } else if (ret == 2) {
          process(arr[0], true);
          process(arr[2], false);
        } else if (ret == 1) {
          process(arr[0], false);
          process(arr[2], true); 
        } else {
          process(arr[0], true);
          process(arr[2], true);
        }
      } else if (arr.size() == 5) {
        if (ret == 4) {
          process(arr[0], false);
          process(arr[2], false);
          process(arr[4], false);
        } else if (ret == 3) {
          // process(arr[2], false);
          // diff[arr[0]].push_back(arr[4]);
          // diff[arr[4]].push_back(arr[0]);
          --pos;
          v[pos] = arr[0];
          --pos;
          v[pos] = arr[4];
          --pos;
          v[pos] = arr[2];
          doNextSimple = true;
        } else if (ret == 2) {
          process(arr[0], true);
          process(arr[2], false);
          process(arr[4], true);
        } else if (ret == 1) {
          // process(arr[2], true);
          // diff[arr[0]].push_back(arr[4]);
          // diff[arr[4]].push_back(arr[0]);
          --pos;
          v[pos] = arr[0];
          --pos;
          v[pos] = arr[4];
          --pos;
          v[pos] = arr[2];
          doNextSimple = true;
        } else {
          process(arr[0], true);
          process(arr[2], true);
          process(arr[4], true);
        }
      }
    } else if (b.size() > 1) {
      vector<int> arr;
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(v[pos]), ++pos;
        arr.push_back(b[0]);
      }
      nextPos(v, pos);
      if (pos < (int) v.size()) {
        arr.push_back(v[pos]), ++pos;
        arr.push_back(b[1]); 
      }
      // if (!doNextSimple) {
      //   nextPos(v, pos);
      //   if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos;
      // }

      doNextSimple = true;
      int ret = use_machine(arr);
      if (arr.size() == 2) {
        if (ret == 1) {
          process(arr[0], true);
        } else {
          process(arr[0], false);
        }
      } else if (arr.size() == 4) {
        if (ret == 3) {
          process(arr[0], true);
          process(arr[2], true);
        } else if (ret == 2) {
          process(arr[0], false);
          process(arr[2], true);
        } else if (ret == 1) {
          process(arr[0], true);
          process(arr[2], false); 
        } else {
          process(arr[0], false);
          process(arr[2], false);
        }
      } else if (arr.size() == 5) {
        if (ret == 4) {
          process(arr[0], true);
          process(arr[2], true);
          process(arr[4], true);
        } else if (ret == 3) {
          process(arr[2], true);
          diff[arr[0]].push_back(arr[4]);
          diff[arr[4]].push_back(arr[0]);
          --pos;
          v[pos] = arr[0];
          doNextSimple = true;
        } else if (ret == 2) {
          process(arr[0], false);
          process(arr[2], true);
          process(arr[4], false);
        } else if (ret == 1) {
          process(arr[2], false);
          diff[arr[0]].push_back(arr[4]);
          diff[arr[4]].push_back(arr[0]);
          --pos;
          v[pos] = arr[0];
          doNextSimple = true;
        } else {
          process(arr[0], false);
          process(arr[2], false);
          process(arr[4], false);
        }
      }
    } else {
      vector<int> arr = {a[0]};
      nextPos(v, pos);
      if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos;
      else break;

      doNextSimple = false;
      int ret = use_machine(arr);
      if (ret & 1) {
        process(arr[1], false);
      } else {
        process(arr[1], true);
      }
    }
  }

  ans = a.size();

  if (a.size() + b.size() != n) exit(-1);

  if (a.size() >= b.size()) {
    while (pos < (int) v.size()) {
      vector<int> arr;
      int used = 0;
      for (int i = 0; i < (int) a.size(); ++i) {
        arr.push_back(a[i]);
        if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos, ++used;
        else break;
      }
      int ret = use_machine(arr);
      int diff = (ret / 2) + (ret & 1);
      ans += used - diff;
    }
  } else {
    while (pos < (int) v.size()) {
      vector<int> arr;
      int used = 0;
      for (int i = 0; i < (int) b.size(); ++i) {
        arr.push_back(b[i]);
        if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos, ++used;
        else break;
      }
      int ret = use_machine(arr);
      int diff = (ret / 2) + (ret & 1);
      ans += diff;
    }
  }

  return ans;
}

// int count_mushrooms(int n) {
//   int ans = 1;
//   for (int i = 1; i < n; i += 2) {
//     vector<int> v;
//     if (i + 1 < n) v = {i, 0, i + 1};
//     else v = {i, 0};
//     int ret = use_machine(v);
//     ans += (v.size() - 1) - ret;
//   }
//   return ans;
// }

// int main() {
//   ios::sync_with_stdio(false);

//   return 0; 
// }

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:215:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  215 |   if (a.size() + b.size() != n) exit(-1);
      |       ~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Partially correct	10 ms	384 KB	Output is partially correct
7	Partially correct	125 ms	1528 KB	Output is partially correct
8	Partially correct	130 ms	1400 KB	Output is partially correct
9	Partially correct	123 ms	1400 KB	Output is partially correct
10	Partially correct	139 ms	1440 KB	Output is partially correct
11	Partially correct	109 ms	1476 KB	Output is partially correct
12	Incorrect	125 ms	1480 KB	Answer is not correct.
13	Halted	0 ms	0 KB	-