| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1066524 | 2024-08-20T00:15:53 Z | myst6 | Ancient Machine 2 (JOI23_ancient2) | C++17 | 43 ms | 1480 KB |
#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_BITS = 1000;
const int BOUND = 54;
#define bs bitset<MAX_BITS>
vector<bs> MIS(const vector<bs>& vectors) {
vector<bs> basis; // Store the basis vectors here
vector<bs> mis;
for (const auto& vec : vectors) {
bs v = vec; // Copy the vector
// Try to eliminate the current vector with the basis vectors
for (const auto& b : basis) {
if (v.none()) break; // If the vector is already zero, skip
if (v.test(b._Find_first())) { // If leading bit matches
v ^= b; // Subtract the basis vector (add in GF(2))
}
}
// If the vector is not zero after elimination, it's linearly independent
if (v.any()) {
basis.push_back(v);
mis.push_back(vec); // Add the original vector to the mis
}
}
return mis;
}
void gaussian_elimination(vector<bs> &A, bs &S, bs &b, int N) {
int row = 0;
for (int col = 0; col < N; ++col) {
// Find pivot row
int pivot = -1;
for (int i = row; i < N; ++i) {
if (A[i][col]) {
pivot = i;
break;
}
}
if (pivot == -1) continue; // No pivot found, move to the next column
// Swap pivot row with the current row
swap(A[row], A[pivot]);
// swap(b[row], b[pivot]);
int tmp = b[row];
b[row] = b[pivot];
b[pivot] = tmp;
// Eliminate below
for (int i = row + 1; i < N; ++i) {
if (A[i][col]) {
A[i] ^= A[row];
// b[i] ^= b[row];
if (b[row]) b[i] = !b[i];
}
}
++row;
}
// Backward substitution
S.reset();
for (int i = row - 1; i >= 0; --i) {
if (A[i].any()) {
int leading_one = A[i]._Find_first();
S[leading_one] = b[i];
for (int j = leading_one + 1; j < N; ++j) {
if (A[i][j]) {
// S[leading_one] ^= S[j];
if (S[j]) S[leading_one] = !S[leading_one];
}
}
}
}
}
string solve(int N, vector<pair<bs,int>> &info) {
// Create bitsets
vector<bs> A(N);
bs S, b;
// Populate the matrix A and vector b with parity information
for (int i=0; i<N; i++) {
A[i] = info[i].first;
b[i] = info[i].second;
}
// Perform Gaussian elimination
gaussian_elimination(A, S, b, N);
// Output the reconstructed binary string
string s = S.to_string();
reverse(s.begin(), s.end());
return s.substr(0, N);
}
string Solve(int N) {
vector<pair<bs,int>> info;
function<int(int,int)> solve1 = [&](int i, int j) -> int {
int m = 2 * j;
vector<int> a(m), b(m);
for (int r=0; r<j; r++) {
a[r] = (r + 1) % j;
b[r] = (r + 1) % j;
a[j + r] = j + ((r + 1) % j);
b[j + r] = j + ((r + 1) % j);
}
b[i] = j + ((i + 1) % j);
b[i + j] = (i + 1) % j;
return Query(m, a, b) / j;
};
function<int(int)> solve2 = [&](int k) -> int {
int m = k + 3;
vector<int> a(m), b(m);
for (int r=0; r<k; r++) {
a[r] = r + 1;
b[r] = r + 1;
}
a[k] = k + 1;
b[k] = k + 2;
a[k + 1] = b[k + 1] = k + 1;
a[k + 2] = b[k + 2] = k + 2;
return Query(m, a, b) - k - 1;
};
vector<bs> all;
vector<array<int,2>> ij;
for (int j=1; j<=BOUND; j++) {
for (int i=0; i<j; i++) {
bs here;
for (int k=i; k<N; k+=j) {
here[k] = 1;
}
all.push_back(here);
ij.push_back({i, j});
}
}
for (int i=0; i<=min(99,N); i++) {
bs here;
here[i] = 1;
all.push_back(here);
}
int A = all.size();
vector<bs> mis = MIS(all);
for (bs &HELP : mis) {
if (HELP.count() == 1) {
int i = HELP._Find_first();
info.push_back({HELP, solve2(i)});
} else {
for (int i=0; i<A; i++) {
if (HELP == all[i]) {
info.push_back({HELP, solve1(ij[i][0], ij[i][1])});
// cout << ij[i][0] << "," << ij[i][1] << "," << solve1(ij[i][0], ij[i][1]) << "\n";
}
}
}
}
// cout << info.size() << "\n";
return solve(N, info);
}
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 2 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 3 | Partially correct | 31 ms | 980 KB | Output is partially correct |
| 4 | Partially correct | 31 ms | 1068 KB | Output is partially correct |
| 5 | Partially correct | 36 ms | 1072 KB | Output is partially correct |
| 6 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 7 | Partially correct | 37 ms | 1100 KB | Output is partially correct |
| 8 | Partially correct | 34 ms | 1076 KB | Output is partially correct |
| 9 | Partially correct | 31 ms | 1100 KB | Output is partially correct |
| 10 | Partially correct | 33 ms | 1080 KB | Output is partially correct |
| 11 | Partially correct | 38 ms | 1092 KB | Output is partially correct |
| 12 | Partially correct | 31 ms | 980 KB | Output is partially correct |
| 13 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 14 | Partially correct | 33 ms | 1200 KB | Output is partially correct |
| 15 | Partially correct | 31 ms | 1228 KB | Output is partially correct |
| 16 | Partially correct | 33 ms | 980 KB | Output is partially correct |
| 17 | Partially correct | 33 ms | 1480 KB | Output is partially correct |
| 18 | Partially correct | 31 ms | 1072 KB | Output is partially correct |
| 19 | Partially correct | 35 ms | 1096 KB | Output is partially correct |
| 20 | Partially correct | 33 ms | 1092 KB | Output is partially correct |
| 21 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 22 | Partially correct | 42 ms | 1092 KB | Output is partially correct |
| 23 | Partially correct | 32 ms | 1072 KB | Output is partially correct |
| 24 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 25 | Partially correct | 37 ms | 1208 KB | Output is partially correct |
| 26 | Partially correct | 32 ms | 1200 KB | Output is partially correct |
| 27 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 28 | Partially correct | 42 ms | 992 KB | Output is partially correct |
| 29 | Partially correct | 32 ms | 1092 KB | Output is partially correct |
| 30 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 31 | Partially correct | 36 ms | 1228 KB | Output is partially correct |
| 32 | Partially correct | 32 ms | 1072 KB | Output is partially correct |
| 33 | Partially correct | 31 ms | 980 KB | Output is partially correct |
| 34 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 35 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 36 | Partially correct | 31 ms | 1236 KB | Output is partially correct |
| 37 | Partially correct | 31 ms | 1092 KB | Output is partially correct |
| 38 | Partially correct | 35 ms | 1088 KB | Output is partially correct |
| 39 | Partially correct | 36 ms | 980 KB | Output is partially correct |
| 40 | Partially correct | 37 ms | 980 KB | Output is partially correct |
| 41 | Partially correct | 32 ms | 1096 KB | Output is partially correct |
| 42 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 43 | Partially correct | 43 ms | 980 KB | Output is partially correct |
| 44 | Partially correct | 33 ms | 1076 KB | Output is partially correct |
| 45 | Partially correct | 32 ms | 1104 KB | Output is partially correct |
| 46 | Partially correct | 42 ms | 980 KB | Output is partially correct |
| 47 | Partially correct | 35 ms | 1088 KB | Output is partially correct |
| 48 | Partially correct | 33 ms | 980 KB | Output is partially correct |
| 49 | Partially correct | 36 ms | 980 KB | Output is partially correct |
| 50 | Partially correct | 34 ms | 1096 KB | Output is partially correct |
| 51 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 52 | Partially correct | 37 ms | 980 KB | Output is partially correct |
| 53 | Partially correct | 33 ms | 980 KB | Output is partially correct |
| 54 | Partially correct | 34 ms | 1084 KB | Output is partially correct |
| 55 | Partially correct | 34 ms | 1236 KB | Output is partially correct |
| 56 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 57 | Partially correct | 41 ms | 1080 KB | Output is partially correct |
| 58 | Partially correct | 32 ms | 980 KB | Output is partially correct |
| 59 | Partially correct | 33 ms | 1084 KB | Output is partially correct |
| 60 | Partially correct | 33 ms | 1092 KB | Output is partially correct |
| 61 | Partially correct | 31 ms | 1092 KB | Output is partially correct |
| 62 | Partially correct | 38 ms | 980 KB | Output is partially correct |
| 63 | Partially correct | 35 ms | 1232 KB | Output is partially correct |