Submission #500970

#	Time	Username	Problem	Language	Result	Execution time	Memory
500970		aryan12	Paint By Numbers (IOI16_paint)	C++17	100 / 100	531 ms	186472 KiB

paint

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

const long long MAXN = 2e5 + 10, MAXK = 110, MOD = 1e9 + 7;
long long canBlack[MAXN], canWhite[MAXN], dp[MAXN][MAXK];
string S;
vector<long long> C;
vector<long long> white;

long long recur(long long s_idx, long long c_idx) {
    //cout << "s_idx = " << s_idx << ", c_idx = " << c_idx << "\n";
    if(s_idx == S.size() && c_idx == C.size()) { //works
        return dp[s_idx][c_idx] = 1;
    }
    if(s_idx >= S.size() || c_idx > C.size()) { //out of bounds
        return 0;
    }
    if(dp[s_idx][c_idx] != -1) {
        return dp[s_idx][c_idx];
    }
    dp[s_idx][c_idx] = 0;
    /*
    Conditions to make this block white:
    Current position shouldn't be black;

    Conditions to make the next Y blocks black:
    There shouldn't be a white block in between;
    The Y+1th block shouldn't be black
    The cur + Yth box should exist
    */

    //to make the block white
    if(S[s_idx] != 'X') {
        long long ok = recur(s_idx + 1, c_idx);
        //cout << "val for immediate = " << ok << "\n";
        //cout << "any valid seq? ";
        if(ok != 0) {
            //cout << "yes\n";
            canWhite[s_idx]++;
            canWhite[s_idx + 1]--;
            dp[s_idx][c_idx] += ok;
        }
        /*else {
            cout << "no\n";
        }*/
    }

    //to make the next Y blocks black
    long long x = lower_bound(white.begin(), white.end(), s_idx) - white.begin();
    long long f1 = 0;
    //so that cur + Y exists
    if(s_idx + C[c_idx] < S.size()) {
        f1++;
    } 
    //for white not in between
    //assert(x <= white.size() && x >= 0);
    if(x == white.size() || white[x] >= s_idx + C[c_idx]) {
        f1++;
    }
    //for Y+1 not black
    //assert(s_idx + C[c_idx] < S.size());
    if(s_idx + C[c_idx] == S.size() || S[s_idx + C[c_idx]] != 'X') {
        f1++;
    }
    if(f1 == 3) { //all conditions satisfied
        long long ok = recur(s_idx + C[c_idx] + 1, c_idx + 1);
        if(ok != 0) {
            canBlack[s_idx]++;
            canBlack[s_idx + C[c_idx]]--;
            canWhite[s_idx + C[c_idx]]++;
            canWhite[s_idx + C[c_idx] + 1]--;
        } 
        dp[s_idx][c_idx] += ok;
    }
    dp[s_idx][c_idx] %= MOD;
    return dp[s_idx][c_idx];
}

string solve_puzzle(string s, vector<int> c) {
    S = s;
    S += "_";
    for(long long i = 0; i < S.size(); i++) {
        if(S[i] == '_') {
            white.push_back(i);
        }
    }
    for(long long i = 0; i < c.size(); i++) {
        C.push_back(c[i]);
    }
    long long n = s.size(), k = c.size();
    for(long long i = 0; i < MAXN; i++) {
        for(long long j = 0; j < MAXK; j++) {
            dp[i][j] = -1;
        }
    }
    long long ok = recur(0, 0);
    /*for(long long i = 0; i < s.size(); i++) {
        for(long long j = 0; j < c.size(); j++) {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }*/
    string ans = "";
    for(long long i = 1; i <= n; i++) {
        canWhite[i] += canWhite[i - 1];
        canBlack[i] += canBlack[i - 1];
    }
    for(long long i = 0; i < n; i++) {
        if(canWhite[i] != 0 && canBlack[i] != 0) {
            ans += "?";
        }
        else if(canWhite[i] != 0 && canBlack[i] == 0) {
            ans += "_";
        }
        else {
            ans += "X";
        }
    }
    return ans;
    return "";
}

Compilation message (stderr)

paint.cpp: In function 'long long int recur(long long int, long long int)':
paint.cpp:13:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if(s_idx == S.size() && c_idx == C.size()) { //works
      |        ~~~~~~^~~~~~~~~~~
paint.cpp:13:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if(s_idx == S.size() && c_idx == C.size()) { //works
      |                             ~~~~~~^~~~~~~~~~~
paint.cpp:16:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     if(s_idx >= S.size() || c_idx > C.size()) { //out of bounds
      |        ~~~~~~^~~~~~~~~~~
paint.cpp:16:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     if(s_idx >= S.size() || c_idx > C.size()) { //out of bounds
      |                             ~~~~~~^~~~~~~~~~
paint.cpp:53:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     if(s_idx + C[c_idx] < S.size()) {
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~
paint.cpp:58:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     if(x == white.size() || white[x] >= s_idx + C[c_idx]) {
      |        ~~^~~~~~~~~~~~~~~
paint.cpp:63:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if(s_idx + C[c_idx] == S.size() || S[s_idx + C[c_idx]] != 'X') {
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:83:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(long long i = 0; i < S.size(); i++) {
      |                          ~~^~~~~~~~~~
paint.cpp:88:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(long long i = 0; i < c.size(); i++) {
      |                          ~~^~~~~~~~~~
paint.cpp:91:29: warning: unused variable 'k' [-Wunused-variable]
   91 |     long long n = s.size(), k = c.size();
      |                             ^
paint.cpp:97:15: warning: unused variable 'ok' [-Wunused-variable]
   97 |     long long ok = recur(0, 0);
      |               ^~

• 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