POJ 3623 - Best Cow Line, Gold

http://poj.org/problem?id=3623

概要

POJ 3617 - Best Cow Line と同じなので略．

ただし制約が N <= 30000 になっているが，Time Limit も伸びているので全く同じ O(N^2) の解法で通る．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int N;
 7   scanf("%d", &N);
 8   static char s[30001];
 9   for (int i = 0; i < N; i++) {
10     scanf("%1s", &s[i]);
11   }
12 
13   static char buf[30001];
14   char *p = buf;
15   for (int beg = 0, end = N-1; beg <= end;) {
16     int b = beg, e = end;
17     while (b <= e && s[b] == s[e]) {
18       b++;
19       e--;
20     }
21     if (s[b] <= s[e]) {
22       *p++ = s[beg++];
23     } else {
24       *p++ = s[end--];
25     }
26   }
27   for (int i = 0; i < N; i += 80) {
28     for (int j = 0; j < 80 && i+j < N; j++) {
29       putchar(buf[i+j]);
30     }
31     putchar('\n');
32   }
33   return 0;
34 }