Submission #1262948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262948		DeltaStruct	Type Printer (IOI08_printer)	C++17	50 / 100	570 ms	4064 KiB

printer

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin >> n; vector<string> A(n); for (auto& a:A) cin >> a;
  sort(A.begin(),A.end());
  auto f = [](string s,string t) -> int {
    int i(0); for (;i < (int)min(s.size(),t.size());++i) if (s[i]!=t[i]) break;
    return s.size()-i+t.size()-i;
  };
  vector<pair<int,int>> R;
  vector<int> B(1),C(1),D(n); B[0] = f("",A[0]),C[0] = f("",A[n-1]);
  for (int i(1);i < n;++i) B.emplace_back(B.back()+f(A[i-1],A[i]));
  for (int i(n-2);i > -1;--i) C.emplace_back(C.back()+f(A[i+1],A[i]));
  reverse(C.begin(),C.end());
  for (int i(0);i < n;++i){
    if (i==0) R.emplace_back(C[0],i);
    else if (i==n-1) R.emplace_back(B[n-1],i);
    else {
      R.emplace_back(B[i-1]+C[i+1]+f(A[i+1],A[i])+f(A[i-1],A[n-1])-f("",A[n-1]),i);
      R.emplace_back(B[i-1]+C[i+1]+f(A[i-1],A[i])+f(A[i+1],A[0])-f("",A[0]),i);
      D[i] = (R.end()[-2]>R.end()[-1]);
    }
  }
  auto ff = [](string s,string t) -> void {
    int i(0); for (;i < (int)min(s.size(),t.size());++i) if (s[i]!=t[i]) break;
    for (int k(i);k < (int)s.size();++k) cout << '-' << endl;
    for (int k(i);k < (int)t.size();++k) cout << t[k] << endl;
    cout << 'P' << endl;
  };
  sort(R.begin(),R.end()); cout << R[0].first+n << endl;
  if (R[0].second==0){
    ff("",A[n-1]); for (int i(n-2);i > -1;--i) ff(A[i+1],A[i]);
  } else if (R[0].second==n-1){
    ff("",A[0]); for (int i(1);i < n;++i) ff(A[i-1],A[i]);
  } else if (D[R[0].second]){
    ff("",A[n-1]);
    for (int i(n-2);i > R[0].second;--i) ff(A[i+1],A[i]);
    ff(A[R[0].second+1],A[0]);
    for (int i(1);i <= R[0].second;++i) ff(A[i-1],A[i]);
  } else {
    ff("",A[0]);
    for (int i(1);i < R[0].second;++i) ff(A[i-1],A[i]);
    ff(A[R[0].second-1],A[n-1]);
    for (int i(n-2);i >= R[0].second;--i) ff(A[i+1],A[i]);
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10