QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369779 | #8505. Almost Aligned | willow# | Compile Error | / | / | C++17 | 3.6kb | 2024-03-28 17:52:46 | 2024-03-28 17:52:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
char s[maxn], t[maxn]; 123
int n, k;
int Check(int x) {
for(int i = 1; i + x <= n; ++ i) {
if(s[i] != s[i + x]) {
return 0;
}
}
return 1;
}
int sh = -1, g;
struct Arr {
int del, rev, who, cnt[maxn];
void Init(int _who) {
del = rev = 0;
who = _who;
fill(cnt, cnt + maxn, 0);
}
void Reverse() {
rev ^= 1;
who ^= 1;
del = -del;
}
void Left(int w) {
if(rev) {
del += w;
}
else {
del -= w;
}
}
void Right(int w) {
if(rev) {
del -= w;
}
else {
del += w;
}
}
void Add(int x) {
cerr << "Add delta = " << del << " rev = " << rev << " who = " << who << " x = " << x << endl;
if(rev) {
++ cnt[((-(del + x)) % g + g) % g];
}
else {
++ cnt[((x - del) % g + g) % g];
}
}
int Query() {
int tar = 0;
if(who) {
if(sh == -1)
return 0;
tar = sh;
}
cerr << "Query tar = " << tar << endl;
if(rev) {
return cnt[((-(del + tar)) % g + g) % g];
}
else {
return cnt[((tar - del) % g + g) % g];
}
}
}a[2];
char op[5];
int fail[maxn];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
g = n;
for(int i = 1; i * i <= n; ++ i) {
if(n % i == 0) {
if(Check(i)) {
g = min(g, i);
}
if(Check(n / i)) {
g = min(g, n / i);
}
}
}
for(int i = 1; i <= n; ++ i) {
t[i] = s[n - i + 1];
}
fail[1] = 0;
int p = 0;
for(int i = 2; i <= n; ++ i) {
while(p && s[i] != s[p + 1])
p = fail[p];
if(s[i] == s[p + 1])
++ p;
fail[i] = p;
}
int now = 0;
for(int i = 1; i <= 2 * n; ++ i) {
while(now && t[i] != s[now + 1])
now = fail[now];
if(t[i] == s[now + 1])
++ now;
if(now == n) {
sh = i - n;
break;
}
}
cerr << g << " " << sh << endl;
a[0].Init(0), a[1].Init(1);
scanf("%d", &k);
long long ans = 0;
for(int i = 1, w; i <= k; ++ i) {
scanf("%s", op + 1);
if(op[1] == 'I') { // reverse
a[0].Reverse();
a[1].Reverse();
if(a[0].who)
a[0].Add(0);
else
a[1].Add(0);
}
else {
scanf("%d", &w);
if(op[1] == 'L') { // to_left w
a[0].Left(w);
a[1].Left(w);
if(!a[0].who)
a[0].Add(g - w);
else
a[1].Add(g - w);
}
else { // to_right w
a[0].Right(w);
a[1].Right(w);
if(!a[0].who)
a[0].Add(w);
else
a[1].Add(w);
}
}
ans += a[0].Query();
ans += a[1].Query();
cerr << "? Right = " << i << " ans = " << ans << endl;
cerr << "a[0]: rev = " << a[0].rev << " delta = " << a[0].del << " who = " << a[0].who << ": ";
for(int i = 0; i < g; ++ i)
cerr << a[0].cnt[i] << " ";
cerr << endl;
cerr << "a[1]: ";
for(int i = 0; i < g; ++ i)
cerr << a[1].cnt[i] << " ";
cerr << endl;
}
printf("%lld\n", ans);
}
Details
answer.code:4:24: error: expected unqualified-id before numeric constant 4 | char s[maxn], t[maxn]; 123 | ^~~ answer.code: In function ‘int Check(int)’: answer.code:7:29: error: ‘n’ was not declared in this scope 7 | for(int i = 1; i + x <= n; ++ i) { | ^ answer.code: In function ‘int main()’: answer.code:72:5: error: ‘n’ was not declared in this scope; did you mean ‘yn’? 72 | n = strlen(s + 1); | ^ | yn answer.code:109:18: error: ‘k’ was not declared in this scope 109 | scanf("%d", &k); | ^ answer.code:71:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 71 | scanf("%s", s + 1); | ~~~~~^~~~~~~~~~~~~ answer.code:112:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 112 | scanf("%s", op + 1); | ~~~~~^~~~~~~~~~~~~~ answer.code:122:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 122 | scanf("%d", &w); | ~~~~~^~~~~~~~~~