제출 #654044

#제출 시각아이디문제언어결과실행 시간메모리
654044ellakass버섯 세기 (IOI20_mushrooms)C++14
100 / 100
9 ms316 KiB
#include <cstdio> #include "mushrooms.h" int count_mushrooms(int n) { std::vector < int > V0 = { 0 }, V1; int a1 = use_machine({ 0, 1 }); if (n == 2) return 2 - a1; int unused = 2, Q = 1; if (a1) { V1.push_back(1); int a2 = use_machine({ 0, 2 }); if (a2) V1.push_back(2); else V0.push_back(2); unused++; Q++; } else V0.push_back(1); while (Q < 82 && std::min(V0.size(), V1.size()) < 3) { if (unused == n) return V0.size(); if (unused == n - 1) return V0.size() + 1 - use_machine({ 0, n - 1 }); if (V0.size() >= 2) { int r = use_machine({ V0[0], unused, V0[1], unused + 1 }); if (r & 2) V1.push_back(unused); else V0.push_back(unused); if (r & 1) V1.push_back(unused + 1); else V0.push_back(unused + 1); unused += 2; } else { int r = use_machine({ V1[0], unused, V1[1], unused + 1 }); if (r & 2) V0.push_back(unused); else V1.push_back(unused); if (r & 1) V0.push_back(unused + 1); else V1.push_back(unused + 1); unused += 2; } Q++; } int op0 = -1, op1 = -1; while (Q < 82) { if (op0 == -1) { if (unused == n) return V0.size(); if (unused == n - 1) return V0.size() + 1 - use_machine({ 0, n - 1 }); if (unused == n - 2) { int r = use_machine({ V0[0], unused, V0[1], unused + 1 }); return V0.size() + !(r & 2) + !(r & 1); } int r = use_machine({ V0[0], unused, V0[1], unused + 1, V0[2], unused + 2 }); if (r & 1) V1.push_back(unused + 2); else V0.push_back(unused + 2); r >>= 1; if (r == 1) { op0 = unused; op1 = unused + 1; } else if (r == 0) { V0.push_back(unused); V0.push_back(unused + 1); } else { V1.push_back(unused); V1.push_back(unused + 1); } unused += 3; } else { if (unused == n) return V0.size() + 1; if (unused == n - 1) return V0.size() + 2 - use_machine({ 0, n - 1 }); int r = use_machine({ unused, V0[0], unused + 1, V0[1], op0, V0[2], V1[0], op1, V1[1] }) - 1; if (r & 1) V1.push_back(unused); else V0.push_back(unused); if (r & 2) V1.push_back(unused + 1); else V0.push_back(unused + 1); if (r & 4) { V1.push_back(op0); V0.push_back(op1); } else { V0.push_back(op0); V1.push_back(op1); } op0 = op1 = -1; unused += 2; } Q++; } int O = V0.size() + (op0 != -1); while (true) { std::vector < int > query; if (V0.size() >= V1.size()) { if (n - unused > V0.size()) { for (int i = 0; i < V0.size(); i++) { query.push_back(V0[i]); query.push_back(unused + i); } int r = use_machine(query); O += V0.size() - (r + 1 >> 1); unused += V0.size(); if (r & 1) V1.push_back(unused - 1); else V0.push_back(unused - 1); } else { int L = n - unused; for (int i = 0; i < L; i++) { query.push_back(V0[i]); query.push_back(unused + i); } return O + L - (use_machine(query) + 1 >> 1); } } else { if (n - unused > V1.size()) { for (int i = 0; i < V1.size(); i++) { query.push_back(V1[i]); query.push_back(unused + i); } int r = use_machine(query); O += r + 1 >> 1; unused += V1.size(); if (r & 1) V0.push_back(unused - 1); else V1.push_back(unused - 1); } else { int L = n - unused; for (int i = 0; i < L; i++) { query.push_back(V1[i]); query.push_back(unused + i); } return O + (use_machine(query) + 1 >> 1); } } } }

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

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    if (n - unused > V0.size())
      |        ~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i < V0.size(); i++)
      |                     ~~^~~~~~~~~~~
mushrooms.cpp:139:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |     O += V0.size() - (r + 1 >> 1);
      |                       ~~^~~
mushrooms.cpp:154:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |     return O + L - (use_machine(query) + 1 >> 1);
      |                     ~~~~~~~~~~~~~~~~~~~^~~
mushrooms.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |    if (n - unused > V1.size())
      |        ~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (int i = 0; i < V1.size(); i++)
      |                     ~~^~~~~~~~~~~
mushrooms.cpp:167:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |     O += r + 1 >> 1;
      |          ~~^~~
mushrooms.cpp:182:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  182 |     return O + (use_machine(query) + 1 >> 1);
      |                 ~~~~~~~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...