I got WA, even though I got Accepted on another on-line judge (with exactly the same source), and I got 100 points at a romanian contest in which it was a similar problem (I tested it with the tests from that contest).
I think the tests are wrong, but still there are some Accepted solutions...
Here is my code:
Code: Select all
#include <cstdio>
#include <cassert>
int n;
inline int next(int s) {
return (s + 1) % n;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("t.in", "rt", stdin);
#endif
const int nmax = 100000;
int ts;
scanf("%d", &ts);
for (int it = 0; it < ts; ++ it) {
scanf("%d", &n);
char s[nmax];
scanf("%s", s);
int w[nmax], t = n;
for (int i = 0; i < n; ++ i)
w[i] = i;
for (; t > 1;) {
int nt = 0;
for (int i = 0; i < t; ++ i) {
if (i + 1 < t) {
int s1 = w[i], s2 = w[i + 1], j = 0;
const int l = s2 - s1;
assert(l > 0);
for (; s[s1] == s[s2] && j < l; ++ j, s1 = next(s1), s2 = next(s2));
if (j < l && s[s1] > s[s2])
w[nt ++] = w[i + 1];
else w[nt ++] = w[i];
++ i;
}
else w[nt ++] = w[i];
}
t = nt;
}
printf("%d\n", w[0]);
}
return 0;
}