Submission #952228

#TimeUsernameProblemLanguageResultExecution timeMemory
952228arbuzickAncient Machine 2 (JOI23_ancient2)C++17
98 / 100
331 ms1324 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) { for (int i = 0; i < 100; ++i) { bs[i][i] = 1; } // for (int i = 0; i < 101; ++i) { // bs[100 + i][n - i - 1] = 1; // } vector<pair<int, int>> qs; for (int a = 0; a < n; ++a) { for (int b = 1; b <= n; ++b) { if (a < b && b * 2 <= 108) { for (int i = 0; i < n; ++i) { if (i >= a && i % b == a % b) { bs[100 + qs.size()][i] = 1; } else { bs[100 + qs.size()][i] = 0; } } if (is_answer(100 + qs.size(), n)) { qs.emplace_back(a, b); } } if (qs.size() == n - 100) { break; } } if (qs.size() == n - 100) { 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 - 100) { return ""; } for (int i = 0; i < 100; ++i) { for (int j = 0; j < n; ++j) { if (j == i) { bs[i][j] = 1; } else { bs[i][j] = 0; } } } // for (int i = 0; i < 101; ++i) { // for (int j = 0; j < n; ++j) { // if (j == n - i - 1) { // bs[100 + i][j] = 1; // } else { // bs[100 + i][j] = 0; // } // } // } for (int i = 0; i < (int)qs.size(); ++i) { for (int j = 0; j < n; ++j) { if (j >= qs[i].first && j % qs[i].second == qs[i].first % qs[i].second) { bs[100 + i][j] = 1; } else { bs[100 + i][j] = 0; } } } for (int i = 0; i < 100; ++i) { vector<int> a(i + 3), b(i + 3); for (int j = 0; j < i; ++j) { a[j] = j + 1; b[j] = j + 1; } a[i] = i + 1; b[i] = i + 2; a[i + 1] = b[i + 1] = i + 1; a[i + 2] = b[i + 2] = i + 2; int val = Query(i + 3, a, b); if (val == i + 1) { bs[i][n] = 0; } else { bs[i][n] = 1; } } for (int i = 0; i < (int)qs.size(); ++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[100 + i][n] = 0; } else { bs[100 + i][n] = 1; } } return get_answer(n); }

Compilation message (stderr)

ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:78: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]
   78 |             if (qs.size() == n - 100) {
      |                 ~~~~~~~~~~^~~~~~~~~~
ancient2.cpp:82: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]
   82 |         if (qs.size() == n - 100) {
      |             ~~~~~~~~~~^~~~~~~~~~
ancient2.cpp:94: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]
   94 |     if (qs.size() != n - 100) {
      |         ~~~~~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...