#include <bits/stdc++.h>
#define MAX_N 25000
#define MAX_LEN 20
using namespace std;
int lcp[MAX_N], len[MAX_N];
string s[MAX_N];
vector <char> sol;
int main() {
int n, minLen, first, last, i, j, l;
bool cresc;
cin >> n;
for ( i = 0; i < n; i++ )
cin >> s[i];
sort( s, s + n );
for ( i = 0; i < n; i++ )
len[i] = s[i].size();
for ( i = 0; i < n; i++ ) {
j = (i + 1) % n;
l = 0;
while ( l < len[i] && l < len[j] && s[i][l] == s[j][l] )
l++;
lcp[i] = l;
}
minLen = MAX_LEN + 1;
last = -1;
cresc = true;
for ( i = 0; i < n; i++ ) {
if ( 2 * lcp[i] - len[i] < minLen ) {
minLen = 2 * lcp[i] - len[i];
last = i;
cresc = true;
}
if ( 2 * lcp[(i - 1 + n) % n] - len[i] < minLen ) {
minLen = 2 * lcp[(i - 1 + n) % n] - len[i];
last = i;
cresc = false;
}
}
if ( cresc ) {
first = (last + 1) % n;
l = 0;
for ( int k = 0; k < n; k++ ) {
i = (first + k) % n;
j = (i - 1 + n) % n;
while ( l > lcp[j] ) {
sol.push_back( '-' );
l--;
}
while ( l < len[i] ) {
sol.push_back( s[i][l] );
l++;
}
sol.push_back( 'P' );
}
} else {
first = (last - 1 + n) % n;
l = 0;
for ( int k = 0; k < n; k++ ) {
i = (first - k + n) % n;
j = (i - 1 + n) % n;
while ( l > lcp[j] ) {
sol.push_back( '-' );
l--;
}
while ( l < len[i] ) {
sol.push_back( s[i][l] );
l++;
}
sol.push_back( 'P' );
}
}
cout << sol.size() << "\n";
for ( char o: sol )
cout << o << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Incorrect |
1 ms |
980 KB |
printed invalid word |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
1108 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
1268 KB |
Output is correct |
2 |
Incorrect |
11 ms |
1592 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
17 ms |
1704 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
2592 KB |
Output is correct |
2 |
Incorrect |
75 ms |
4516 KB |
printed invalid word |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
34 ms |
2156 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |