제출 #1263068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263068		DeltaStruct	Type Printer (IOI08_printer)	C++17	70 / 100	658 ms	6332 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;
  };
  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;
  };
  vector<int> B(26);
  for (int i(0);i < 26;++i){
    string s; for (int k(0);k < n;++k) if (A[k][0]-'a'!=i) B[i] += f(s,A[k]),s = A[k];
    B[i] += f(s,"");
  }
  vector<vector<string>> C(26); for (auto a:A) C[a[0]-'a'].emplace_back(a);
  vector D(26,vector<int>(1)),E = D; vector<tuple<int,int,int,int>> R;
  for (int i(0);i < 26;++i) if (!C[i].empty()){
    int m = C[i].size();
    D[i][0] = f("",C[i][0]),E[i][0] = f("",C[i][m-1]);
    for (int k(1);k < m;++k) D[i].emplace_back(D[i].back()+f(C[i][k-1],C[i][k]));
    for (int k(m-2);k > -1;--k) E[i].emplace_back(E[i].back()+f(C[i][k+1],C[i][k]));
    reverse(E[i].begin(),E[i].end());
    for (int k(0);k < m;++k){
      if (k==0) R.emplace_back(B[i]+E[i][0],i,k,-1);
      else if (k==m-1) R.emplace_back(B[i]+D[i][m-1],i,k,-1);
      else {
        R.emplace_back(B[i]+D[i][k-1]+E[i][k]+f(C[i][k-1],C[i][m-1])-f("",C[i][m-1]),i,k,0);
        R.emplace_back(B[i]+D[i][k]+E[i][k+1]+f(C[i][k+1],C[i][0])-f("",C[i][0]),i,k,1);
        R.emplace_back(B[i]+D[i][m-1]-f(C[i][k-1],C[i][k])-f(C[i][k],C[i][k+1])+f(C[i][m-1],C[i][k])+f(C[i][k-1],C[i][k+1]),i,k,2);
        R.emplace_back(B[i]+E[i][0]-f(C[i][k+1],C[i][k])-f(C[i][k],C[i][k-1])+f(C[i][0],C[i][k])+f(C[i][k+1],C[i][k-1]),i,k,3);
      }
    }
  }
  sort(R.begin(),R.end()); auto [a,i,k,t] = R[0]; int m = C[i].size(); cout << a+n << endl;
  string s; for (int j(0);j < n;++j) if (A[j][0]-'a'!=i) ff(s,A[j]),s = A[j];
  if (k==0){
    for (int j(m-1);j > -1;--j) ff(s,C[i][j]),s = C[i][j];
  } else if (k==m-1){
    for (int j(0);j < m;++j) ff(s,C[i][j]),s = C[i][j];
  } else if (t==0){
    for (int j(0);j < k;++j) ff(s,C[i][j]),s = C[i][j];
    for (int j(m-1);j >= k;--j) ff(s,C[i][j]),s = C[i][j];
  } else if (t==1){
    for (int j(m-1);j > k;--j) ff(s,C[i][j]),s = C[i][j];
    for (int j(0);j <= k;++j) ff(s,C[i][j]),s = C[i][j];
  } else if (t==2){
    for (int j(0);j < m;++j) if (j!=k) ff(s,C[i][j]),s = C[i][j];
    ff(s,C[i][k]);
  } else {
     for (int j(m-1);j > -1;--j) if (j!=k) ff(s,C[i][j]),s = C[i][j];
    ff(s,C[i][k]);
  }
}

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