Submission #289096

#	Time	Username	Problem	Language	Result	Execution time	Memory
289096		MladenP	Paint By Numbers (IOI16_paint)	C++17	100 / 100	245 ms	83756 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define sz(x) int((x).size())
using namespace std;
#define MAXN 200010
#define MAXK 110
int lBeli[MAXN], rBeli[MAXN], b[MAXN], c[MAXN];
bool dpLK[MAXK][MAXN], dpRK[MAXK][MAXN], dpL[MAXK][MAXN], dpR[MAXK][MAXN];
std::string solve_puzzle(std::string s, std::vector<int> C) {
    s = "%" + s + "%";
    int N = sz(s)-2, K = sz(C);
    lBeli[0] = 0;
    for(int i = 1; i <= N; i++) lBeli[i] = (s[i] == '_' ? i:lBeli[i-1]);
    rBeli[N+1] = N+1;
    for(int i = N; i >= 1; i--) rBeli[i] = (s[i] == '_' ? i:rBeli[i+1]);
    ///dpL
    dpL[0][0] = true;
    for(int i = 1; i <= N; i++) {
      dpL[0][i] = (dpL[0][i-1] && s[i] != 'X');
      dpLK[0][i] = true;
    }
    for(int j = 1; j <= K; j++) {
      dpLK[j][0] = false;
      for(int i = 1; i <= N; i++) {
        if(!(lBeli[i] <= i-C[j-1] && s[i-C[j-1]] != 'X')) dpLK[j][i] = false;
        else if(i-C[j-1] == 0) dpLK[j][i] = (j == 1 ? true:false);
        else dpLK[j][i] = dpL[j-1][i-C[j-1]-1];
        dpL[j][i] = ((dpL[j][i-1]&&s[i]!='X')||dpLK[j][i]);
      }
    }
    ///dpR
    dpR[0][N+1] = true;
    for(int i = N; i >= 1; i--) {
      dpR[0][i] = (dpR[0][i+1] && s[i] != 'X');
      dpRK[0][i] = true;
    }
    for(int j = 1; j <= K; j++) {
      dpRK[j][N+1] = false;
      dpR[j][N+1] = false;
      for(int i = N; i >= 1; i--) {
        if(!(rBeli[i] >= i+C[K-j] && s[i+C[K-j]] != 'X')) dpRK[j][i] = false;
        else if(i+C[K-j] == N+1) dpRK[j][i] = (j == 1 ? true:false);
        else dpRK[j][i] = dpR[j-1][i+C[K-j]+1];
        dpR[j][i] = ((dpR[j][i+1]&&s[i]!='X')||dpRK[j][i]);
      }
    }
    ///da li moze beo
    for(int i = 1; i <= N; i++) {
      if(s[i] == 'X') continue;
      if(s[i] == '_') {
        b[i] = true;
        continue;
      }
      for(int j = 0; j <= K; j++) {
        if(dpL[j][i-1] && dpR[K-j][i+1]) {
          b[i] = true;
          break;
        }
      }
    }
    ///da li moze crn
    for(int j = 1; j <= K; j++) {
      int duz = C[j-1], posl = 1000000000;
      for(int i = N; i >= 1; i--) {
        if(dpLK[j][i] && s[i+1] != 'X') {
          if(i == N && j == K) posl = i;
          else if(i != N && dpR[K-j][i+2]) posl = i;
        }
        if(posl <= i+duz-1) c[i] = true;
      }
    }
    string res = "";
    for(int i = 1; i <= N; i++) {
      if(b[i] && c[i]) res += '?';
      else if(b[i]) res += '_';
      else if(c[i]) res += 'X';
    }
    return res;
}

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