Submission #945206

#TimeUsernameProblemLanguageResultExecution timeMemory
945206ifateenKoala Game (APIO17_koala)C++17
47 / 100
41 ms728 KiB
#include <bits/stdc++.h> #include "koala.h" using namespace std; int minValue(int N, int W) { // TODO: Implement Subtask 1 solution here. // You may leave this function unmodified if you are not attempting this // subtask. int b[N], r[N]; memset(b, 0, sizeof(b)); b[0] = 1; playRound(b, r); if (r[0] <= 1) { // he couldnt care less to take this return 0; } // he could sad for (int i = 1; i < N; i++) { if (r[i] == 0) return i; } } int maxValue(int N, int W) { // TODO: Implement Subtask 2 solution here. // You may leave this function unmodified if you are not attempting this // subtask. vector<int> possible(N); iota(begin(possible), end(possible), 0); int b[N], r[N]; while (possible.size() > 1) { int add = W / possible.size(); memset(b, 0, sizeof(b)); for (auto& i : possible) b[i] = add; playRound(b, r); possible.clear(); for (int i = 0; i < N; i++) if (r[i] > add) possible.push_back(i); } return possible[0]; } int greaterValue(int N, int W) { // TODO: Implement Subtask 3 solution here. // You may leave this function unmodified if you are not attempting this // subtask. int b[N], R[N]; memset(b, 0, sizeof(b)); int l = 1, r = 13; while (l <= r) { int mid = (l + r) >> 1; b[0] = mid, b[1] = mid; playRound(b, R); if (min(R[0], R[1]) > mid /*he took both so idk*/) l = mid + 1; else if (max(R[0], R[1]) <= mid /*he took neither so spend less lol*/) r = mid - 1; else { if (R[0] < R[1]) return 1; else return 0; } } assert(false); } vector<int> ind; int n, w; bool compare(int i, int j) { // is i < j? int b[n], r[n]; memset(b, 0, sizeof(b)); b[i] = w / 2, b[j] = w / 2; playRound(b, r); return (r[j] * 2) > w; } vector<int> merge_sort(int l, int r) { if (l == r) return vector<int>(1, l); int mid = (l + r) >> 1; auto left = merge_sort(l, mid), right = merge_sort(mid + 1, r); vector<int> ret; int i = 0, j = 0; while (i < left.size() && j < right.size()) { if (compare(left[i], right[j])) ret.push_back(left[i++]); else ret.push_back(right[j++]); } while (i < left.size()) ret.push_back(left[i++]); while (j < right.size()) ret.push_back(right[j++]); return ret; } void allValues(int N, int W, int *P) { n = N, w = W; if (W == 2*N) { // TODO: Implement Subtask 4 solution here. // You may leave this block unmodified if you are not attempting this // subtask. ind.resize(N); iota(begin(ind), end(ind), 0LL); auto ans = merge_sort(0, N - 1); for (int i = 0; i < N; i++) P[ans[i]] = i + 1; } else { // TODO: Implement Subtask 5 solution here. // You may leave this block unmodified if you are not attempting this // subtask. } }

Compilation message (stderr)

koala.cpp: In function 'std::vector<int> merge_sort(int, int)':
koala.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     while (i < left.size() && j < right.size()) {
      |            ~~^~~~~~~~~~~~~
koala.cpp:80:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     while (i < left.size() && j < right.size()) {
      |                               ~~^~~~~~~~~~~~~~
koala.cpp:84:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     while (i < left.size()) ret.push_back(left[i++]);
      |            ~~^~~~~~~~~~~~~
koala.cpp:85:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     while (j < right.size()) ret.push_back(right[j++]);
      |            ~~^~~~~~~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
   20 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...