#include "ancient2.h"
#include<bits/stdc++.h>
namespace {
int variable_example = 1;
std::vector<std::pair<int, int>> basis = {
{0,1},{0,2},{0,3},{1,3},{0,4},{1,4},{0,5},{1,5},{2,5},{3,5},{0,6},{1,6},{0,7},{1,7},{2,7},{3,7},{4,7},{5,7},{0,8},{1,8},{2,8},{3,8},{0,9},{1,9},{2,9},{3,9},{4,9},{5,9},{0,10},{1,10},{2,10},{3,10},{0,11},{1,11},{2,11},{3,11},{4,11},{5,11},{6,11},{7,11},{8,11},{9,11},{0,12},{1,12},{2,12},{3,12},{0,13},{1,13},{2,13},{3,13},{4,13},{5,13},{6,13},{7,13},{8,13},{9,13},{10,13},{11,13},{0,14},{1,14},{2,14},{3,14},{4,14},{5,14},{0,15},{1,15},{2,15},{3,15},{4,15},{5,15},{6,15},{7,15},{0,16},{1,16},{2,16},{3,16},{4,16},{5,16},{6,16},{7,16},{0,17},{1,17},{2,17},{3,17},{4,17},{5,17},{6,17},{7,17},{8,17},{9,17},{10,17},{11,17},{12,17},{13,17},{14,17},{15,17},{0,18},{1,18},{2,18},{3,18},{4,18},{5,18},{0,19},{1,19},{2,19},{3,19},{4,19},{5,19},{6,19},{7,19},{8,19},{9,19},{10,19},{11,19},{12,19},{13,19},{14,19},{15,19},{16,19},{17,19},{0,20},{1,20},{2,20},{3,20},{4,20},{5,20},{6,20},{7,20},{0,21},{1,21},{2,21},{3,21},{4,21},{5,21},{6,21},{7,21},{8,21},{9,21},{10,21},{11,21},{0,22},{1,22},{2,22},{3,22},{4,22},{5,22},{6,22},{7,22},{8,22},{9,22},{0,23},{1,23},{2,23},{3,23},{4,23},{5,23},{6,23},{7,23},{8,23},{9,23},{10,23},{11,23},{12,23},{13,23},{14,23},{15,23},{16,23},{17,23},{18,23},{19,23},{20,23},{21,23},{0,24},{1,24},{2,24},{3,24},{4,24},{5,24},{6,24},{7,24},{0,25},{1,25},{2,25},{3,25},{4,25},{5,25},{6,25},{7,25},{8,25},{9,25},{10,25},{11,25},{12,25},{13,25},{14,25},{15,25},{16,25},{17,25},{18,25},{19,25},{0,26},{1,26},{2,26},{3,26},{4,26},{5,26},{6,26},{7,26},{8,26},{9,26},{10,26},{11,26},{0,27},{1,27},{2,27},{3,27},{4,27},{5,27},{6,27},{7,27},{8,27},{9,27},{10,27},{11,27},{12,27},{13,27},{14,27},{15,27},{16,27},{17,27},{0,28},{1,28},{2,28},{3,28},{4,28},{5,28},{6,28},{7,28},{8,28},{9,28},{10,28},{11,28},{0,29},{1,29},{2,29},{3,29},{4,29},{5,29},{6,29},{7,29},{8,29},{9,29},{10,29},{11,29},{12,29},{13,29},{14,29},{15,29},{16,29},{17,29},{18,29},{19,29},{20,29},{21,29},{22,29},{23,29},{24,29},{25,29},{26,29},{27,29},{0,30},{1,30},{2,30},{3,30},{4,30},{5,30},{6,30},{7,30},{0,31},{1,31},{2,31},{3,31},{4,31},{5,31},{6,31},{7,31},{8,31},{9,31},{10,31},{11,31},{12,31},{13,31},{14,31},{15,31},{16,31},{17,31},{18,31},{19,31},{20,31},{21,31},{22,31},{23,31},{24,31},{25,31},{26,31},{27,31},{28,31},{29,31},{0,32},{1,32},{2,32},{3,32},{4,32},{5,32},{6,32},{7,32},{8,32},{9,32},{10,32},{11,32},{12,32},{13,32},{14,32},{15,32},{0,33},{1,33},{2,33},{3,33},{4,33},{5,33},{6,33},{7,33},{8,33},{9,33},{10,33},{11,33},{12,33},{13,33},{14,33},{15,33},{16,33},{17,33},{18,33},{19,33},{0,34},{1,34},{2,34},{3,34},{4,34},{5,34},{6,34},{7,34},{8,34},{9,34},{10,34},{11,34},{12,34},{13,34},{14,34},{15,34},{0,35},{1,35},{2,35},{3,35},{4,35},{5,35},{6,35},{7,35},{8,35},{9,35},{10,35},{11,35},{12,35},{13,35},{14,35},{15,35},{16,35},{17,35},{18,35},{19,35},{20,35},{21,35},{22,35},{23,35},{0,36},{1,36},{2,36},{3,36},{4,36},{5,36},{6,36},{7,36},{8,36},{9,36},{10,36},{11,36},{0,37},{1,37},{2,37},{3,37},{4,37},{5,37},{6,37},{7,37},{8,37},{9,37},{10,37},{11,37},{12,37},{13,37},{14,37},{15,37},{16,37},{17,37},{18,37},{19,37},{20,37},{21,37},{22,37},{23,37},{24,37},{25,37},{26,37},{27,37},{28,37},{29,37},{30,37},{31,37},{32,37},{33,37},{34,37},{35,37},{0,38},{1,38},{2,38},{3,38},{4,38},{5,38},{6,38},{7,38},{8,38},{9,38},{10,38},{11,38},{12,38},{13,38},{14,38},{15,38},{16,38},{17,38},{0,39},{1,39},{2,39},{3,39},{4,39},{5,39},{6,39},{7,39},{8,39},{9,39},{10,39},{11,39},{12,39},{13,39},{14,39},{15,39},{16,39},{17,39},{18,39},{19,39},{20,39},{21,39},{22,39},{23,39},{0,40},{1,40},{2,40},{3,40},{4,40},{5,40},{6,40},{7,40},{8,40},{9,40},{10,40},{11,40},{12,40},{13,40},{14,40},{15,40},{0,41},{1,41},{2,41},{3,41},{4,41},{5,41},{6,41},{7,41},{8,41},{9,41},{10,41},{11,41},{12,41},{13,41},{14,41},{15,41},{16,41},{17,41},{18,41},{19,41},{20,41},{21,41},{22,41},{23,41},{24,41},{25,41},{26,41},{27,41},{28,41},{29,41},{30,41},{31,41},{32,41},{33,41},{34,41},{35,41},{36,41},{37,41},{38,41},{39,41},{0,42},{1,42},{2,42},{3,42},{4,42},{5,42},{6,42},{7,42},{8,42},{9,42},{10,42},{11,42},{0,43},{1,43},{2,43},{3,43},{4,43},{5,43},{6,43},{7,43},{8,43},{9,43},{10,43},{11,43},{12,43},{13,43},{14,43},{15,43},{16,43},{17,43},{18,43},{19,43},{20,43},{21,43},{22,43},{23,43},{24,43},{25,43},{26,43},{27,43},{28,43},{29,43},{30,43},{31,43},{32,43},{33,43},{34,43},{35,43},{36,43},{37,43},{38,43},{39,43},{40,43},{41,43},{0,44},{1,44},{2,44},{3,44},{4,44},{5,44},{6,44},{7,44},{8,44},{9,44},{10,44},{11,44},{12,44},{13,44},{14,44},{15,44},{16,44},{17,44},{18,44},{19,44},{0,45},{1,45},{2,45},{3,45},{4,45},{5,45},{6,45},{7,45},{8,45},{9,45},{10,45},{11,45},{12,45},{13,45},{14,45},{15,45},{16,45},{17,45},{18,45},{19,45},{20,45},{21,45},{22,45},{23,45},{0,46},{1,46},{2,46},{3,46},{4,46},{5,46},{6,46},{7,46},{8,46},{9,46},{10,46},{11,46},{12,46},{13,46},{14,46},{15,46},{16,46},{17,46},{18,46},{19,46},{20,46},{21,46},{0,47},{1,47},{2,47},{3,47},{4,47},{5,47},{6,47},{7,47},{8,47},{9,47},{10,47},{11,47},{12,47},{13,47},{14,47},{15,47},{16,47},{17,47},{18,47},{19,47},{20,47},{21,47},{22,47},{23,47},{24,47},{25,47},{26,47},{27,47},{28,47},{29,47},{30,47},{31,47},{32,47},{33,47},{34,47},{35,47},{36,47},{37,47},{38,47},{39,47},{40,47},{41,47},{42,47},{43,47},{44,47},{45,47},{0,48},{1,48},{2,48},{3,48},{4,48},{5,48},{6,48},{7,48},{8,48},{9,48},{10,48},{11,48},{12,48},{13,48},{14,48},{15,48},{0,49},{1,49},{2,49},{3,49},{4,49},{5,49},{6,49},{7,49},{8,49},{9,49},{10,49},{11,49},{12,49},{13,49},{14,49},{15,49},{16,49},{17,49},{18,49},{19,49},{20,49},{21,49},{22,49},{23,49},{24,49},{25,49},{26,49},{27,49},{28,49},{29,49},{30,49},{31,49},{32,49},{33,49},{34,49},{35,49},{36,49},{37,49},{38,49},{39,49},{40,49},{41,49},{0,50},{1,50},{2,50},{3,50},{4,50},{5,50},{6,50},{7,50},{8,50},{9,50},{10,50},{11,50},{12,50},{13,50},{14,50},{15,50},{16,50},{17,50},{18,50},{19,50},{0,51},{1,51},{2,51},{3,51},{4,51},{5,51},{6,51},{7,51},{8,51},{9,51},{10,51},{11,51},{12,51},{13,51},{14,51},{15,51},{16,51},{17,51},{18,51},{19,51},{20,51},{21,51},{22,51},{23,51},{24,51},{25,51},{26,51},{27,51},{28,51},{29,51},{30,51},{0,52},{1,52},{2,52},{3,52},{4,52},{5,52},{6,52},{7,52},{8,52},{9,52},{10,52},{11,52},{31,51},{12,52},{13,52},{14,52},{15,52},{16,52},{17,52},{18,52},{19,52},{20,52},{21,52},{22,52},{23,52},{0,53},{1,53},{2,53},{3,53},{4,53},{5,53},{6,53},{7,53},{8,53},{9,53},{10,53},{11,53},{12,53},{13,53},{14,53},{15,53},{16,53},{17,53},{18,53},{19,53},{20,53},{21,53},{22,53},{23,53},{24,53},{25,53},{26,53},{27,53},{28,53},{29,53},{30,53},{31,53},{32,53},{33,53},{34,53},{35,53},{36,53},{37,53},{38,53},{39,53},{40,53},{41,53},{42,53},{43,53},{44,53},{45,53},{0,54},{1,54},{2,54},{3,54},{4,54},{5,54},{6,54},{7,54},{8,54},{9,54},{10,54},{11,54},{12,54},{13,54},{14,54},{15,54},{16,54},{17,54},{0,55},{1,55},{2,55},{3,55},{4,55},{5,55},{6,55},{7,55},{8,55},{9,55},{46,53},{47,53},{48,53},{49,53},{50,53},{51,53},{10,55},{11,55},{12,55},{13,55},{14,55},{15,55},{16,55},{17,55},{18,55},{19,55},{20,55},{21,55},{22,55},{23,55},{24,55},{25,55},{26,55},{27,55},{28,55},{29,55},{30,55},{31,55},{32,55},{33,55},{34,55},{35,55},{36,55},{37,55},{38,55},{39,55},{0,56},{1,56},{2,56},{3,56},{4,56},{5,56},{6,56},{7,56},{8,56},{9,56},{10,56},{11,56},{12,56},{13,56},{14,56},{15,56},{16,56},{17,56},{18,56},{19,56},{20,56},{21,56},{22,56},{23,56},{0,57},{1,57},{2,57},{3,57},{4,57},{5,57},{6,57},{7,57},{8,57},{9,57},{10,57},{11,57},{12,57},{13,57},{14,57},{15,57},{16,57},{17,57},{18,57},{19,57},{20,57},{21,57},{22,57},{23,57},{24,57},{25,57},{26,57},{27,57},{28,57},{29,57},{30,57},{0,58},{1,58},{2,58},{3,58},{6,58}
};
std::vector<std::bitset<1001>> bs;
} // namespace
int Xor(int n, int o) {
int m = n+n;
std::vector<int> a(m), b(m);
for (int i = 0; i < n; ++i) {
a[i] = i+1;
b[i] = i+1;
}
a[n-1] = 0; b[n-1] = 0;
for (int i = n; i < m; ++i) {
a[i] = i+1;
b[i] = i+1;
}
a[m-1] = n; b[m-1] = n;
std::swap(b[o], b[o+n]);
int r = Query(m, a, b);
return r >= n;
}
std::string Solve(int N) {
for (auto& [o, n] : basis) {
bs.emplace_back(std::bitset<1001>(0));
bs.back().reset();
for (int i = 0; i * n + o < 1000; ++i) {
bs.back().set(i*n+o);
}
int a = Xor(n, o);
if (a) bs.back().set(1000);
}
std::vector where(1000, -1);
std::vector ans(1000, 0);
for (int c = 0, r = 0; c < 1000 && r < bs.size(); ++c) {
for (int i = r; i < bs.size(); ++i) {
if (bs[i][c]) {
std::swap(bs[i], bs[r]);
break;
}
}
if (!bs[r][c]) continue;
where[c] = r;
for (int i = 0; i < bs.size(); ++i) {
if (i != r && bs[i][c]) bs[i] ^= bs[r];
}
++r;
}
for (int i = 0; i < 1000; ++i) {
if (where[i] == -1) continue;
int r = where[i];
if (bs[r].count() == 2) ans[i] = 1;
}
std::string s = "";
for (int i = 0; i < 1000; ++i) {
if (ans[i]) s += "1";
else s += "0";
}
return s;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |