#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//Autor: Michał Szeliga
#ifdef LOCAL
#define debug(...) __VA_ARGS__;
#else
#define debug(...) {}
#endif
#define read(...) debug((void)!freopen(__VA_ARGS__,"r",stdin););
const int M = 1001;
bitset<M> akt[M-1];
int ile = 0;
int gauss(bitset<M> x){
int i;
for (i = 0; i < M-1; i++){
if (x[i]){
if (!akt[i][i]){
//cout<<i<<" # "<<x<<"\n";
akt[i] = x;
ile++;
return i;
}
x ^= akt[i];
}
}
return -1;
}
bool policz(int x){
bitset<M> wy;
wy[x] = 1;
for (int i = 0; i < M-1; i++){
if (wy[i]) wy ^= akt[i];
}
return wy[M-1];
}
void stworz_automat(int c, int r){
bitset<M> wy;
for (int i = r; i < M-1; i += c) wy[i] = 1;
int id = gauss(wy);
if (id != -1){
int m = 2*c;
vector<int> A,B;
for (int i = 0; i < c; i++){
if ((i+1)%c == r){
A.push_back(r);
B.push_back(c+r);
}else{
A.push_back((i+1)%c);
B.push_back((i+1)%c);
}
}
for (int i = c; i < 2*c; i++){
if ((i+1)%c == r){
A.push_back(r);
B.push_back(c+r);
}else{
A.push_back(c+(i+1)%c);
B.push_back(c+(i+1)%c);
}
}
akt[id][M-1] = (Query(m,A,B) >= c);
}
}
string Solve(int n){
for (int c = 1; c < M-1; c++){
for (int r = 0; r < c; r++){
stworz_automat(c,r);
if (ile == M-1) break;
}
}
string wy;
for (int i = 0; i < n; i++){
if (policz(i)) wy += '1';
else wy += '0';
}
return wy;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
1280 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
