Submission #952211

#TimeUsernameProblemLanguageResultExecution timeMemory
952211arbuzickAncient Machine 2 (JOI23_ancient2)C++17
97 / 100
353 ms1272 KiB
#include "ancient2.h" #include <bits/stdc++.h> using namespace std; bitset<1001> bs[1000]; bool is_answer(int pos, int n) { for (int i = 0; i < pos; ++i) { for (int j = 0; j < n; ++j) { if (bs[i][j]) { if (bs[pos][j]) { bs[pos] ^= bs[i]; } break; } } } for (int j = 0; j < n; ++j) { if (bs[pos][j]) { for (int i = 0; i < pos; ++i) { if (bs[i][j]) { bs[i] ^= bs[pos]; } } return true; } } return false; } 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 && b * 2 <= 114) { 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(), n)) { qs.emplace_back(a, b); } } if (qs.size() == n) { break; } } if (qs.size() == n) { break; } } // cout << "{"; // for (int i = 0; i < n; ++i) { // cout << "{" << qs[i].first << ", " << qs[i].second << "}"; // if (i + 1 < n) { // cout << ", "; // } // } // cout << "}"; 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].second * 2), b(qs[i].second * 2); for (int j = 0; j < qs[i].second; ++j) { if (j + 1 == qs[i].second) { a[j] = b[j] = 0; a[qs[i].second + j] = b[qs[i].second + j] = qs[i].second; } else { a[j] = b[j] = j + 1; a[qs[i].second + j] = b[qs[i].second + j] = qs[i].second + j + 1; } } b[qs[i].first] += qs[i].second; b[qs[i].first + qs[i].second] -= qs[i].second; int val = Query(qs[i].second * 2, a, b); if (val < 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:72: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]
   72 |             if (qs.size() == n) {
      |                 ~~~~~~~~~~^~~~
ancient2.cpp:76: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]
   76 |         if (qs.size() == n) {
      |             ~~~~~~~~~~^~~~
ancient2.cpp:88: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]
   88 |     if (qs.size() != n) {
      |         ~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...