Submission #952195

#TimeUsernameProblemLanguageResultExecution timeMemory
952195arbuzickAncient Machine 2 (JOI23_ancient2)C++17
64 / 100
649 ms1668 KiB
#include "ancient2.h" #include <bits/stdc++.h> using namespace std; bitset<1001> bs[1000]; bool is_answer(int cnt, int n) { for (int i = 0; i < cnt; ++i) { int pos = -1; for (int j = i; j < cnt; ++j) { if (bs[j][i]) { pos = j; break; } } if (pos == -1) { return false; } swap(bs[i], bs[pos]); for (int j = 0; j < cnt; ++j) { if (j != i && bs[j][i]) { bs[j] ^= bs[i]; } } } return true; } string get_answer(int n) { string ans = ""; for (int i = 0; i < n; ++i) { int pos = -1; for (int j = i; j < n; ++j) { if (bs[j][i]) { pos = j; break; } } swap(bs[i], bs[pos]); for (int j = 0; j < n; ++j) { if (j != i && bs[j][i]) { bs[j] ^= bs[i]; } } } for (int i = 0; i < n; ++i) { ans += '0' + bs[i][n]; } return ans; } string Solve(int n) { vector<pair<int, int>> qs; for (int a = 0; a < n; ++a) { for (int b = 1; b <= n; ++b) { if (a + b * 2 <= 302) { for (int i = 0; i < n; ++i) { if (i >= a && i % b == a % b) { bs[qs.size()][i] = 1; } else { bs[qs.size()][i] = 0; } } if (is_answer(qs.size() + 1, n)) { qs.emplace_back(a, b); } } if (qs.size() == n) { break; } } if (qs.size() == n) { break; } } if (qs.size() != n) { return ""; } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (j >= qs[i].first && j % qs[i].second == qs[i].first % qs[i].second) { bs[i][j] = 1; } else { bs[i][j] = 0; } } } for (int i = 0; i < n; ++i) { vector<int> a(qs[i].first + qs[i].second * 2), b(qs[i].first + qs[i].second * 2); for (int j = 0; j < qs[i].first; ++j) { a[j] = b[j] = j + 1; } for (int j = 0; j < qs[i].second; ++j) { if (j + 1 == qs[i].second) { a[qs[i].first + j] = b[qs[i].first + j] = qs[i].first; a[qs[i].first + qs[i].second + j] = b[qs[i].first + qs[i].second + j] = qs[i].first + qs[i].second; } else { a[qs[i].first + j] = b[qs[i].first + j] = qs[i].first + j + 1; a[qs[i].first + qs[i].second + j] = b[qs[i].first + qs[i].second + j] = qs[i].first + qs[i].second + j + 1; } } b[qs[i].first] = qs[i].first + qs[i].second + 1; b[qs[i].first + qs[i].second] = qs[i].first + 1; if (qs[i].second == 1) { b[qs[i].first]--; b[qs[i].first + qs[i].second]--; } int val = Query(qs[i].first + qs[i].second * 2, a, b); if (val < qs[i].first + qs[i].second) { bs[i][n] = 0; } else { bs[i][n] = 1; } } return get_answer(n); }

Compilation message (stderr)

ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:70:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |             if (qs.size() == n) {
      |                 ~~~~~~~~~~^~~~
ancient2.cpp:74:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         if (qs.size() == n) {
      |             ~~~~~~~~~~^~~~
ancient2.cpp:78:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |     if (qs.size() != n) {
      |         ~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...