Submission #172532

#	Time	Username	Problem	Language	Result	Execution time	Memory
172532		Nightlight	Paint By Numbers (IOI16_paint)	C++14	100 / 100	944 ms	177972 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5+5;
const int maxk = 105;

int visit[maxn][maxk];
int memo[maxn][maxk];
string ans, A;
vector<int> seg;
int suf[maxn], isi[maxn], kosong[maxn];
int N, K;

int dp(int idx, int left) {
//  cout << idx << " " << left << '\n';
  if(idx > N) return 0;
  if(idx == N) return left == K;
  if(memo[idx][left] != -1) return memo[idx][left];
  int res = 0;
  if(A[idx] != 'X')
    res = res || dp(idx + 1, left);
  if(left < K && seg[left] <= suf[idx] && A[idx + seg[left]] != 'X') {
    if(idx + seg[left] + 1 <= N){
      res = res || dp(idx + seg[left] + 1, left + 1);
    }else {
      res = res || dp(idx + seg[left], left + 1);
    }
  }
  return memo[idx][left] = res;
}

void search(int idx, int left) {
  if(idx >= N || visit[idx][left])return;
  visit[idx][left] = 1;
  if(A[idx] != 'X' && dp(idx + 1, left)) {
    kosong[idx] = 1;
    search(idx + 1, left);
  }
  if(left < K && seg[left] <= suf[idx] && A[idx + seg[left]] != 'X' && dp(idx + seg[left] + (idx + seg[left] + 1 <= N), left + 1)) {
    isi[idx]++;
    isi[idx + seg[left]]--;
    kosong[idx + seg[left]] = 1;
    search(idx + seg[left] + 1, left + 1);
  } 
}

string solve_puzzle(string s, vector<int> c) {
  A = s; seg = c;
  N = s.size(); K = c.size();
//  cout << N << " " << K << "\n";
  for(int i = N - 1; i >= 0; i--) {
    suf[i] = (A[i] == '_' ? 0 : 1 + suf[i + 1]);
  }
  memset(memo, -1, sizeof(memo));
  dp(0, 0);
  search(0, 0);
  int state = 0;
  ans.resize(N);
  for(int i = 0; i < N; i++) {
    state += isi[i];
    if(kosong[i] && state > 0) {
      ans[i] = '?';
    }else if(kosong[i]) {
      ans[i] = '_';
    }else if(state > 0) {
      ans[i] = 'X';
    }
  }
  return ans;
}

• 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