제출 #67450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67450		mirbek01	Paint By Numbers (IOI16_paint)	C++17	59 / 100	11 ms	620 KiB

paint

#include "paint.h"
//#include "grader.cpp"

#include <bits/stdc++.h>

using namespace std;

int n, k;

string solve_puzzle(string s, vector<int> c) {
      n = (int)(s.size());
      k = (int)(c.size());
      string ans, t;
      int sum = 0;
      for(int i = 0; i < k; i ++)
            sum += c[i];
      sum += max(0, k - 1);
      if(sum == n){
            for(int i = 0; i < k; i ++){
                  for(int j = 0; j < c[i]; j ++){
                        ans += 'X';
                  }
                  if(i != k - 1){
                        ans += '_';
                  }
            }
      } else {
            vector <int> v;
            int pos = 0;
            for(int i = 0; i < k; i ++){
                  for(int j = 0; j < n; j ++){
                        bool fl = 1;
                        for(int w = pos + j, cn = 0; cn < c[i]; w ++, cn ++){
                              if(s[w] != '.') {
                                    fl = 0;
                                    break;
                              }
                        }
                        if(fl){
                              v.push_back(pos + j);
                              pos = pos + j + c[i] + 1;
                              break;
                        }
                  }
            }
            ans = s;
            t = s;
            for(int i = k - 1; i >= 0; i --){
                  int mx = 0, all = 0;
                  int cnt[n];
                  memset(cnt, 0, sizeof(cnt));
                  for(int j = v[i]; j + c[i] - 1 < n; j ++){
                        bool fl = 1;
                        for(int w = j, cn = 0; cn < c[i]; w ++, cn ++){
                              if(t[w] != '.'){
                                    fl = 0;
                                    break;
                              }
                              if(cn == c[i] - 1){
                                    if(w + 1 < n && t[w + 1] == 'X') fl = 0;
                              }
                        }
                        if(fl){
                              all ++;
                              for(int w = j, cn = 0; cn < c[i]; w ++, cn ++){
                                    cnt[w] ++;
                              }
                              mx = j;
                        }
                  }
                  for(int j = v[i]; j < mx + c[i]; j ++){
                        if(cnt[j] == all)
                              ans[j] = 'X';
                        else if(cnt[j])
                              ans[j] = '?';
                        else if(ans[j] == '.')
                              ans[j] = '_';
                  }
                  for(int j = mx; j < n; j ++){
                        t[j] = 'X';
                  }
            }
      }
      for(int i = 0; i < n; i ++){
            if(ans[i] == '.') ans[i] = '_';
      }
      return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10