Submission #130501

#	Time	Username	Problem	Language	Result	Execution time	Memory
130501		win11905	Paint By Numbers (IOI16_paint)	C++11	80 / 100	168 ms	85112 KiB

paint

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

const int N = 2e5+5;

int n, k;
int pref_[N], prefX[N];
bool fin[105][N];
int canX[N], can_[N];
int st[105][N];
int state[105][N];
char arr[N];
int sz[N];

string solve_puzzle(string s, vector<int> C) {
    memset(state, -1, sizeof state);
    n = s.size(), k = C.size();
    for(int i = 0; i < n; ++i) arr[i+2] = s[i];
    for(int i = 0; i < k; ++i) sz[i+1] = C[i];
    for(int i = 2; i <= n+1; ++i) pref_[i] = pref_[i-1] + (arr[i] == '_' ? 1 : 0);
    for(int i = 2; i <= n+1; ++i) prefX[i] = prefX[i-1] + (arr[i] == 'X' ? 1 : 0);
    pref_[n+2] = pref_[n+1], prefX[n+2] = prefX[n+1];
    state[0][0] = true;
    for(int i = 1; i <= k; ++i) {
        int lst = -1;
        for(int j = sz[i]+1; j <= n+1; ++j) {
            if(state[i-1][j-sz[i]-1] != -1) lst = j-sz[i]-1; 
            if(lst != -1 && (prefX[j-sz[i]] - prefX[lst] == 0) && (pref_[j] - pref_[j-sz[i]] == 0)
                && (prefX[(i == k ? n : j) + 1] - prefX[j] == 0)) state[i][j] = lst;
        }
    }
    for(int i = k; i >= 1; --i) {
        for(int j = n+1; j > 1; --j) {
            if(i == k) st[i][j] = n+1;
            if(st[i][j] == 0) st[i][j] = st[i][j+1];
            if(state[i][j] != -1 && prefX[st[i][j]] - prefX[j] == 0 && st[i][j]) {
                canX[j-sz[i]+1]++, canX[j+1]--;
                can_[j+1]++, can_[st[i][j]+1]--;
                can_[state[i][j]+1]++, can_[j-sz[i]+1]--;
                st[i-1][state[i][j]] = j - sz[i];
            }
        }
    }
    for(int j = 2; j <= n+1; ++j) canX[j] += canX[j-1], can_[j] += can_[j-1];
    string str;
    for(int j = 2; j <= n+1; ++j) {
        if(canX[j] && can_[j]) str.push_back('?');
        else if(canX[j]) str.push_back('X');
        else str.push_back('_');
    }
    return str;
}

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