Submission #852329

#	Time	Username	Problem	Language	Result	Execution time	Memory
852329		tmncollins	Paint By Numbers (IOI16_paint)	C++14	10 / 100	2032 ms	704 KiB

paint

#include <iostream>
#include <deque>
#include <algorithm>
#include <vector>
#include <fstream>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <map>
#include <chrono>
#include <string>
#include <tuple>
#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

const int SIZE = 200001;
const int SMALL_SIZE = 101;
const int YES = 1;
const int NO = -1;
const int UNSURE = 0;
array<int, SIZE> mem;
vector<int> yes_pos, no_pos, yes_run_len;
int n, s;
map<pair<int, int>, int> dpmem;
array<vector<int>, SMALL_SIZE> valid_place;

int can_place(int run_ptr, int yes_ptr, int no_ptr, int i) {

    // base case
    if (run_ptr >= (int) yes_run_len.size()) return 1;
    if (i >= n) return 0;

    // dpmem
    pair<int, int> dp = {run_ptr, i};
    int dp_val = dpmem[dp];
    if (dp_val != 0) {
        if (dp_val > 0) return dp_val;
        return 0;
    }

    // can we place this section here?
    int end = i + yes_run_len[run_ptr];
    dp_val = 0;
    int do_place = 0, dont_place = 0;

    // choose not to place
    if (yes_ptr >= (int) yes_pos.size() || i != yes_pos[yes_ptr]) {
        int no_ptr_2  = no_ptr;

        if (no_ptr < (int) no_pos.size()  && no_pos[no_ptr] == i)   no_ptr_2++;
        dont_place = can_place(run_ptr, yes_ptr, no_ptr_2, i+1);
    }

    // is there a NO in this section?
    if (end <= n && (no_ptr >= (int) no_pos.size() || no_pos[no_ptr] >= end)) {
        // place here 
        while (yes_ptr < (int) yes_pos.size() && yes_pos[yes_ptr] <= end) yes_ptr++;
        while (no_ptr < (int) no_pos.size() && no_pos[no_ptr] <= end) no_ptr++;
        
        // make sure the next position is not a YES
        if (yes_ptr >= (int) yes_pos.size() || yes_pos[yes_ptr] > end) {
            do_place = can_place(run_ptr+1, yes_ptr, no_ptr, end+1);
            if (do_place) valid_place[run_ptr].push_back(i);
        }
    }

    // save dpmem and return
    dp_val = do_place + dont_place;
    dpmem[dp] = dp_val;
    return dp_val;
}

string solve_puzzle(string str, vector<int> arr) {

    yes_run_len = arr;
  	s = (int) arr.size();
    n = (int) str.size();

    // count and set up where we can place
    int ans = can_place(0, 0, 0, 0);
    //
    vector<pair<int, int>> sections;
    for (int k = 0; k < s; k++) {
        int right = valid_place[k][0] + yes_run_len[k];
        bool contiguous = true;
        int last = valid_place[k][0];
        for (int i = 1; i < (int) valid_place[k].size(); i++) {
            if (valid_place[k][i] != valid_place[k][i-1] - 1) {
                // non contiguous placement
                contiguous = false;

                sections.push_back({valid_place[k][i-1], last + yes_run_len[k] - 1});
                last = valid_place[k][i];
            }
        }
        sections.push_back({valid_place[k].back(), last + yes_run_len[k] - 1});
        if (contiguous) {
            int left = valid_place[k].back();
            for (int x = right - yes_run_len[k]; x < left + yes_run_len[k]; x++) mem[x] = YES; // this has to be yes
        }
    }

    sort(sections.begin(), sections.end());

    for (int x = 0; x < sections[0].first; x++) mem[x] = NO;
    for (int k = 1; k < (int) sections.size(); k++) {
        for (int x = sections[k-1].second+1; x < sections[k].first; x++) mem[x] = NO;
    }
    for (int x = sections.back().second+1; x < n; x++) mem[x] = NO;

    // output
    string output = "";
    for (int k = 0; k < n; k++) {
        if (mem[k] == YES) output += "X";
        else if (mem[k] == NO) output += "_";
        else output += "?";
    }

    return output;

}

/*

10 2
??????????
3 4

ans:
6
??X???XX??

*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:84:9: warning: unused variable 'ans' [-Wunused-variable]
   84 |     int ans = can_place(0, 0, 0, 0);
      |         ^~~

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