Submission #415207

#	Time	Username	Problem	Language	Result	Execution time	Memory
415207		ly20	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	356 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
const int MAXN = 110;
string resp;
pair <int, int> v[MAXN];
string solve_puzzle(string s, vector<int> c) {
    resp.resize(s.size());
    int n = s.size();
    int k = c.size();
    int at = 0;
    for(int i = 0; i < n; i++) {
        bool ok = true;
        if(at == k) break;
        for(int j = 0; j < c[at]; j++) {
            if(s[j + i] == '_') ok = false;
        }
        if(ok) {
            v[at].first = i;
            i = i + c[at] ;
            at++;
        }
    }
    at = k - 1;
    for(int i = n - 1; i >= 0; i--) {
        bool ok = true;
        if(at == -1) break;
        for(int j = 0; j < c[at]; j++) {
            if(s[i - j] == '_') ok = false;
        }
        if(ok) {
            v[at].second = i;
            i = i - c[at];
            at--;
        }
    }
    //printf("%d %d\n", v[0].first, v[0].second);
    for(int i = 0; i < n; i++) resp[i] = '_';
    for(int i = 0; i < k; i++) {
        //printf("%d %d\n", v[i].first, v[i].second);
        for(int j = v[i].second - c[i] + 1; j <= v[i].first + c[i] - 1; j++) resp[j] = 'X';
        /*for(int j = v[i].first; j < v[i].first + c[i]; j++) if(resp[j] != 'X') resp[j] = '?';
        for(int j = v[i].second - c[i] + 1; j <= v[i].second; j++) if(resp[j] != 'X') resp[j] = '?';*/
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) {
            if(c[j] + i - 1 >= n) continue;
            bool ok = true;
            for(int l = 0; l < c[j]; l++) {
                if(s[l + i] == '_') ok = false;
            }
            if(!ok) continue;
            if(j != 0 && c[j - 1] + v[j - 1].first - 1 >= i - 1) continue;
            if(j != k - 1 && v[j + 1].second - c[j + 1]  + 1 <= i + c[j]) continue;
            for(int l = 0; l < c[j]; l++) if(resp[l + i] == '_') resp[l + i] = '?';
        }
    }
    return resp;
}

• 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