Submission #590820

#	Time	Username	Problem	Language	Result	Execution time	Memory
590820		Sam_a17	Paint By Numbers (IOI16_paint)	C++14	100 / 100	993 ms	359388 KiB

paint

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;

#define ll long long
#define ld long double

#define all(x) (x.begin(), x.end())
#define rall(x) (x.rbegin(), x.rend())
#define sz(x) (int)x.size()

const int N = 2e5 + 10, K = 1e2 + 10;
int dp[N][K][2], C[N], n, k;
int dp2[N][K][2], p[N];
string curr;

// 1 is if true
// -1 is if undef
// 0 if false

int rec(int st, int ki, int flag) {
  if(st == n && ki == k) {
    return 1;
  } else if(st == n) {
    dp[st][ki][flag] = 0;
    return 0;
  }

  if(dp[st][ki][flag] != -1) {
    return dp[st][ki][flag];
  }

  int answ = 0;
  if(ki != k) {
    int lst = st, lstX = -1;
      if(curr[st + 1] != 'X') {
        int cur = rec(st + 1, ki, 0);
        if(cur) {
          dp2[st + 1][ki][0]++;
        }
        answ |= cur;
      }
      
      int i = st + C[ki + 1];
      if(i <= n && !flag && !(p[i] - p[st])) {
        int curr =  rec(i, ki + 1, 1);
        if(curr) {
          int prefStart = i - C[ki + 1] + 1, prefEnd = i + 1;
          dp2[prefStart][ki + 1][1]++;
          dp2[prefEnd][ki + 1][1]--;
        }
        answ |= curr;
      }
  } else {
      if(curr[st + 1] == 'X') {
        dp[st][ki][flag] = 0;
        return dp[st][ki][flag];
      }
      int cur = rec(st + 1, ki, 0);
      if(cur) {
        dp2[st + 1][ki][0]++;
      }
      answ |= cur;
  }

  dp[st][ki][flag] = answ;
  return dp[st][ki][flag];
}

string solve_puzzle(string s, vector<int> c) {
  memset(dp, -1, sizeof(dp));

  n = sz(s);
  curr += ".";
  for(int i = 0; i < n; i++) {
    curr += s[i];
    p[i + 1] = p[i];
    if(s[i] == '_') {
      p[i + 1]++;
    }
  }

  k = sz(c);
  for(int i = 0; i < k; i++) {
    C[i + 1] = c[i];
  }

  rec(0, 0, 0);

  string answ = "";

  for(int i = 1; i <= n; i++) {
    int cnt1 = 0, cnt2 = 0;
    for(int j = 0; j <= k; j++) {
      dp2[i][j][1] += dp2[i - 1][j][1];
    }

    for(int j = 0; j <= k; j++) {
      if(dp2[i][j][0]) {
        cnt1++;
      }
      if(dp2[i][j][1]) {
        cnt2++;
      }

      if(cnt1 && cnt2) {
        break;
      }
    }
    if(cnt1 && !cnt2) {
      answ += "_";
    } else if(!cnt1 && cnt2) {
      answ += "X";
    } else {
      answ += "?";
    }
  }

  return answ;
}

Compilation message (stderr)

paint.cpp: In function 'int rec(int, int, int)':
paint.cpp:36:9: warning: unused variable 'lst' [-Wunused-variable]
   36 |     int lst = st, lstX = -1;
      |         ^~~
paint.cpp:36:19: warning: unused variable 'lstX' [-Wunused-variable]
   36 |     int lst = st, lstX = -1;
      |                   ^~~~

• 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