Submission #66973

#	Time	Username	Problem	Language	Result	Execution time	Memory
66973		Talant	Paint By Numbers (IOI16_paint)	C++17	59 / 100	3 ms	860 KiB

paint

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

#include <bits/stdc++.h>

#define pb push_back
#define sc second
#define fr first
#define mk make_pair

using namespace std;

const int N = (1e6 + 5);
const int inf = (1e9 + 7);

string ans;
int p[N];
int sf[N];
int id;
int u[N][3];

string solve_puzzle(string s, vector<int> c) {
      int n = s.size();
      int sz = c.size();

      sf[sz] = n - 1;
      id = sz - 1;

      for (int i = n - 1; i >= 0; i --) {
            int cn = 0;
            if (id < 0) break;
            for (int j = min(i,sf[id + 1]); j >= 0; j --) {
                  if (s[j] != '_') cn ++;
                  else break;
                  if (cn == c[id]) {
                        for (int o = j; o <= min(i,sf[id + 1]); o ++)
                              u[o][1] = 1;
                        if (j - 1 >= 0 && s[j - 1] == '.')
                              u[j - 1][2] = 1;

                        sf[id] = j - 2,id --;
                        break;
                  }
            }

      }
      id = 0;
      for (int i = 0; i < n; i ++) {
            int cn = 0;
            for (int j = max(i,(id > 0 ? p[id - 1] : 0)); j < n; j ++) {
                  if (s[j] != '_') cn ++;
                  else break;
                  if (cn == c[id]) {
                        for (int o = max(i,(id > 0 ? p[id - 1] : 0)); o <= j; o ++)
                              u[o][1] = 1;
                        if (j + 1 < n && s[j + 1] == '.')
                              u[j + 1][2] = 1;

                        p[id] = j + 2,id ++;
                        break;
                  }
            }
      }
      for (int i = 0; i < sz; i ++){
            int cur = c[i];
            int l = 0,r = sf[i + 1];

            if (i == 0) l = 0;
            else l = p[i - 1];

            for (int j = l; j <= r - cur + 1; j ++) {
                  int cn = 0;
                  for (int o = j; o <= j + cur - 1; o ++)
                        if (s[o] == '.') cn ++;

                  if (cn == cur) {
                        for (int o = j; o <= j + cur - 1; o ++)
                              u[o][1] = 1;
                        for (int o = l; o <= j - 1; o ++)
                              if (s[o] == '.')
                                    u[o][2] = 1;
                        for (int o = j + cur; o <= r; o ++)
                              if (s[o] == '.')
                                    u[o][2] = 1;
                  }
            }
      }
      for (int i = 0; i < n; i ++) {
            if (u[i][1] && u[i][2]) ans += '?';
            else if (u[i][1]) ans += 'X';
            else ans += '_';
      }
      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