QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#953563 | #10204. Heretical … Möbius | sckrt | TL | 4ms | 3840kb | C++20 | 2.4kb | 2025-03-27 21:17:04 | 2025-03-27 21:17:04 |
Judging History
answer
#include <bits/stdc++.h>
#define test(x) cout<<#x<<" = "<<x<<endl
#define endl '\n'
#define int long long
using namespace std;
const int MAXN = 1e6 + 100, N = 1e9;
int n, m;
string s;
int a[3] = {4, 9, 25}, res[3];
int isp[MAXN];
vector<int> pm;
void pre() {
int NN = sqrt(1e9) + 10;
for (int i = 2; i <= NN; ++i) {
if (isp[i] == 0)
pm.push_back(i);
for (auto p : pm) {
if (i * p > NN)
break;
isp[i * p] = 1;
if (i % p == 0)
break;
}
}
}
void solve() {
n = 200, m = 44100;
{
string s0;
for (int i = 1; i <= 10; ++i) {
cin >> s0;
s += s0;
}
}
auto chk2 = [&](int k) -> bool {
vector<int> vis(210, 1);
for (auto p : pm) {
int pp = p * p, t = k % pp;
t = (pp - t) % pp;
while (t < 200) {
vis[t] = 0;
t += pp;
}
}
for (int i = 0; i < 200; ++i)
if (vis[i] != s[i] - '0')
return 0;
return 1;
};
int vis[50] = {0};
for (int i = 0; i < 3; ++i)
for (int st = 0; st < a[i]; ++st) {
int ok = 1;
for (int j = st; j < n; j += a[i])
if (s[j] == '1') {
ok = 0;
break;
}
if (ok) {
if (res[i] > 0) {
cout << "-1";
return;
}
res[i] = st;
}
}
for (int st = 0; st < 49; ++st) {
int ok = 1;
for (int j = st; j < n; j += 49)
if (s[j] == '1') {
ok = 0;
break;
}
if (ok) {
vis[(49 - st) % 49] = 1;
}
}
vector<int> ast, ans;
for (int st = 1; st <= m; ++st) {
int ok = 1;
for (int i = 0; i < 3; ++i)
if ((st + res[i]) % a[i] != 0)
ok = 0;
if (vis[st % 49] == 0)
ok = 0;
if (ok)
ast.push_back(st);
}
for (int st : ast)
for (int i = st; i <= 1e9; i += m) {
if (chk2(i)) {
ans.push_back(i);
break;
}
}
if (ans.size() == 0)
cout << "-1";
else {
sort(ans.begin(), ans.end());
cout << ans[0];
}
}
signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
pre();
int tt = 1;
// cin >> tt;
while (tt--)
solve();
}
/*
11101110011011101010
11100100111011101110
11100110001010101110
11001110111011001110
01101110101011101000
11101110111011100110
01100010111011001110
11101100101001101110
10101110010011001110
11101110011011101010
01010101010101010101
10101010101010101010
01010101010101010101
10101010101010101010
01010101010101010101
10101010101010101010
01010101010101010101
10101010101010101010
01010101010101010101
10101010101010101010
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
11101110011011101010 11100100111011101110 11100110001010101110 11001110111011001110 01101110101011101000 11101110111011100110 01100010111011001110 11101100101001101110 10101110010011001110 11101110011011101010
output:
1
result:
ok "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010 01010101010101010101 10101010101010101010
output:
-1
result:
ok "-1"
Test #3:
score: 0
Accepted
time: 4ms
memory: 3712kb
input:
11011101110011011101 01011101100111010101 11011100110111010101 10011001110111011101 11001001110101011101 10011101010010011100 11011101010111010001 11011101110111001101 10010101010110011101 11001101110011011101
output:
5201314
result:
ok "5201314"
Test #4:
score: -100
Time Limit Exceeded
input:
00110111010001110110 01010111011100010010 01110101011101100101 01110111011000110111 01000111011001110111 01110111001101110101 01110110011000110011 01110011011101010101 01100111001101110111 00100101010101110110