Submission #192188

#	Time	Username	Problem	Language	Result	Execution time	Memory
192188		FieryPhoenix	Paint By Numbers (IOI16_paint)	C++11	59 / 100	6 ms	412 KiB

paint

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N,K,arr[105];
int earliest[105],latest[105];
int sum[200001];
int black[200005],white[200005];

int query(int l, int r){
  return sum[r]-((l==0)?0:sum[l-1]);
}

string solve_puzzle(string s, vector<int>v){
  N=s.length();
  K=v.size();
  for (int i=0;i<K;i++)
    arr[i+1]=v[i];
  for (int i=0;i<N;i++){
    if (s[i]=='_')
      sum[i]++;
    if (i>0) sum[i]+=sum[i-1];
  }
  int cur=1;
  for (int i=0;i<N;i++){
    if (query(i,i+arr[cur]-1)==0 && (i+arr[cur]==N || s[i+arr[cur]]!='B')){
      earliest[cur]=i+arr[cur]-1;
      i+=arr[cur];
      cur++;
      if (cur>K)
	break;
    }
  }
  cur=K;
  for (int i=N-1;i>=0;i--){
    if (query(i-arr[cur]+1,i)==0 && (i-arr[cur]==0 || s[i-arr[cur]]!='B')){
      latest[cur]=i-arr[cur]+1;
      i-=arr[cur];
      cur--;
      if (cur<0)
	break;
    }
  }
  earliest[0]=-2;
  latest[K+1]=N+1;
  for (int i=1;i<=K;i++){
    int l=earliest[i-1]+2;
    int r=latest[i+1]-2;
    for (int j=l;j+arr[i]-1<=r;j++)
      if (query(j,j+arr[i]-1)==0){
	black[j]++;
	black[j+arr[i]]--;
	white[max(0,l-1)]++;
	white[j]--;
	white[j+arr[i]]++;
	white[r+2]--;
      }
  }

  for (int i=1;i<N;i++){
    white[i]+=white[i-1];
    black[i]+=black[i-1];
  }
  for (int i=0;i<N;i++)
    if (s[i]=='.'){
      if (white[i]==0)
	s[i]='X';
      else if (black[i]==0)
	s[i]='_';
      else
	s[i]='?';
    }
  return s;
}

• 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