fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int N;
  9.     if (!(cin >> N)) return 0;
  10.     string A, B, C; // A = S_S (숭돌), B = S_K (고돌), C = S_H (한돌)
  11.     cin >> A >> B >> C;
  12.  
  13.     // 빠른 불가능 판정: 두 사람이 제출한 문자열이 완전히 같으면 두 사람의 최종 점수는 항상 같다.
  14.     if (A == B || A == C || B == C) {
  15.         cout << -1 << '\n';
  16.         return 0;
  17.     }
  18.  
  19.     // 각 패턴별 인덱스 수집
  20.     vector<int> eq, ab, bc, ac, distinct;
  21.     eq.reserve(N); ab.reserve(N); bc.reserve(N); ac.reserve(N); distinct.reserve(N);
  22.  
  23.     for (int i = 0; i < N; ++i) {
  24.         char a = A[i], b = B[i], c = C[i];
  25.         if (a == b && b == c) {
  26.             eq.push_back(i);                   // 모두 같음: (0,0) 외에는 불가능
  27.         } else if (a == b) {
  28.             ab.push_back(i);                   // a=b!=c : (0,+1) 또는 (0,-1)
  29.         } else if (b == c) {
  30.             bc.push_back(i);                   // b=c!=a : (+1,0) 또는 (-1,0)
  31.         } else if (a == c) {
  32.             ac.push_back(i);                   // a=c!=b : (+1,-1) 또는 (-1,+1)
  33.         } else {
  34.             distinct.push_back(i);             // 모두 다름: (+1,0), (-1,+1), (0,-1)
  35.         }
  36.     }
  37.  
  38.     long long c2 = (long long)ab.size(); // a=b
  39.     long long c3 = (long long)bc.size(); // b=c
  40.     long long c4 = (long long)ac.size(); // a=c
  41.     long long c1 = (long long)distinct.size();
  42.  
  43.     // y(=K-H)를 +로 만들 수 있는 자원이 하나도 없으면 불가능
  44.     if (c2 + c1 + c4 == 0) {
  45.         cout << -1 << '\n';
  46.         return 0;
  47.     }
  48.  
  49.     // 선택할 개수들
  50.     long long p = c2;        // ab에서 (0,+1)로 모두 사용 (y 버퍼를 많이 확보해두면 유리하고 x에는 영향 없음)
  51.     long long v1 = 0;        // distinct에서 (-1,+1) 사용 개수
  52.     long long u  = 0;        // ac에서 (-1,+1) 사용 개수
  53.     // p가 0이라면 y를 올리기 위해 v1 또는 u를 1개는 써야 한다.
  54.     if (p == 0) {
  55.         if (c1 == 0 && c4 == 0) {
  56.             cout << -1 << '\n';
  57.             return 0;
  58.         }
  59.         if (c4 > 0) u = 1;           // x에 덜 불리(-1)하므로 가능하면 ac의 (-1,+1)부터 사용
  60.         else v1 = 1;                 // ac가 없다면 distinct의 (-1,+1)
  61.     }
  62.  
  63.     long long y_now = p + v1 + u;    // 현재 y = K-H
  64.     long long x_pre = -v1 - u;       // 현재 x = S-K (아직 +로 올리기 전)
  65.     long long need_x = 1 - x_pre;    // 목표 x>=1을 위한 추가 필요량
  66.  
  67.     long long avail_u1 = c1 - v1;    // distinct에서 (+1,0)로 쓸 수 있는 남은 개수
  68.     long long avail_r  = c3;         // bc에서 (+1,0)
  69.     long long max_t    = min(c4 - u, max(0LL, y_now - 1)); // ac에서 (+1,-1)로 쓸 수 있는 상한( y≥1 유지 )
  70.  
  71.     long long a1 = min(avail_u1, need_x); need_x -= a1;    // distinct의 (+1,0)
  72.     long long a3 = min(avail_r , need_x); need_x -= a3;    // bc의 (+1,0)
  73.     long long a4 = min(max_t   , need_x); need_x -= a4;    // ac의 (+1,-1)
  74.  
  75.     if (need_x > 0) {
  76.         cout << -1 << '\n';
  77.         return 0;
  78.     }
  79.  
  80.     // 실제 정답 문자열 구성
  81.     string S(N, '?');
  82.  
  83.     auto pick_other = [&](char a, char b, char c)->char {
  84.         for (char ch = 'a'; ch <= 'z'; ++ch) {
  85.             if (ch != a && ch != b && ch != c) return ch;
  86.         }
  87.         return 'a'; // 도달 불가이지만 형식상
  88.     };
  89.  
  90.     // 1) a=b(!=c) : 전부 (0,+1)로 사용 (p == c2)
  91.     for (int idx : ab) S[idx] = A[idx];
  92.  
  93.     // 2) b=c(!=a) : 앞에서 a3개는 (+1,0) 위해 A[idx], 나머지는 이후에 'other'
  94.     for (int i = 0; i < (int)bc.size(); ++i) {
  95.         int idx = bc[i];
  96.         if (i < a3) S[idx] = A[idx];        // (+1,0)
  97.     }
  98.  
  99.     // 3) a=c(!=b) : 앞에서 u개는 (-1,+1) 위해 B[idx], 다음 a4개는 (+1,-1) 위해 A[idx]
  100.     for (int i = 0; i < (int)ac.size(); ++i) {
  101.         int idx = ac[i];
  102.         if (i < u) S[idx] = B[idx];                  // (-1,+1)
  103.         else if (i < u + a4) S[idx] = A[idx];        // (+1,-1)
  104.         // 나머지는 이후에 'other'
  105.     }
  106.  
  107.     // 4) 모두 다름 : 앞에서 v1개는 (-1,+1) 위해 B[idx], 다음 a1개는 (+1,0) 위해 A[idx]
  108.     for (int i = 0; i < (int)distinct.size(); ++i) {
  109.         int idx = distinct[i];
  110.         if (i < v1) S[idx] = B[idx];                 // (-1,+1)
  111.         else if (i < v1 + a1) S[idx] = A[idx];       // (+1,0)
  112.         // 나머지는 이후에 'other'
  113.     }
  114.  
  115.     // 5) 나머지 미배정 위치는 모두 'other' 문자로 채움 (어느 누구에게도 점수 주지 않음)
  116.     for (int i = 0; i < N; ++i) {
  117.         if (S[i] == '?') S[i] = pick_other(A[i], B[i], C[i]);
  118.     }
  119.  
  120.     // 안전 검증: S가 정말로 S>K>H인지 확인. 아니면 -1 출력.
  121.     int scS = 0, scK = 0, scH = 0;
  122.     for (int i = 0; i < N; ++i) {
  123.         if (S[i] == A[i]) ++scS;
  124.         if (S[i] == B[i]) ++scK;
  125.         if (S[i] == C[i]) ++scH;
  126.     }
  127.     if (!(scS > scK && scK > scH)) {
  128.         cout << -1 << '\n';
  129.         return 0;
  130.     }
  131.  
  132.     cout << S << '\n';
  133.     return 0;
  134. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
5
aaaaa
aaaab
aaaac
stdout 
-1
https://ideone.com/wSZu0D
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!