Submission #618838

#	Time	Username	Problem	Language	Result	Execution time	Memory
618838		Dremix10	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	724 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = "<<x.F<<"-"<<x.S<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pp(x) {}
    #define pv(x) {}
    #define ppv(x) {}
#endif
const int N = 105;
const int MOD = 1e9+7;
const ll INF = 1e18+5;


vector<vector<bool> > v;
vector<int> c,arr;
string s;

bool dp[N][N][N];

void solve(int i, int j, int rem){
    p2(i,j)
    if(i == arr.size())
        return;
    if(dp[i][j][rem])return;
    if(arr[i] != 2){
        /// todo - fix when gaps will break flow
        //v[i][arr[i]] = true;
        //solve(i+1,j);
        return;
    }
    /// can choose what to put (white = gap, black = consecutive block)
    if(j < c.size()){
        for(int k=0;k<c[j];k++)
            v[i+k][1] = true;
        bool add = j + 1 < c.size();
        if(add)
            v[i+c[j]][0] = true;
        solve(i+c[j]+add,j+1,rem);
    }
    if(rem > 0){
        v[i][0] = true;
        solve(i+1,j,rem-1);
    }
    dp[i][j][rem] = true;
}

std::string solve_puzzle(std::string S, std::vector<int> C) {
    s = S;
    c = C;

    int n = s.size();
    int m = c.size();

    arr.resize(n);

    int i,j;

    for(i=0;i<n;i++){
        if(s[i] == '_')
            arr[i] = 0;
        else if(s[i] == 'X')
            arr[i] = 1;
        else{
            assert(s[i] == '.');
            arr[i] = 2;
        }
    }
    pv(arr)

    int sum = 0;

    for(auto x : c)
        sum += x;

    int gaps = n - sum;

    assert(gaps >= m-1);

    gaps -= m-1;

    // there are (gaps + m) choose (m) ways to put the gaps

    //rem = gaps;
    v.assign(n,vector<bool>(2,false));

    solve(0,0,gaps);

    string ans = "";

    for(i=0;i<n;i++){
        p(i)
        p2(v[i][0],v[i][1])
        if(v[i][0] == v[i][1]){

            assert(v[i][0] != false);
            ans += '?';
        }
        else if(v[i][0]){
            ans += '_';
        }
        else{
            ans += 'X';
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'void solve(int, int, int)':
paint.cpp:37:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(i == arr.size())
      |        ~~^~~~~~~~~~~~~
paint.cpp:47:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if(j < c.size()){
      |        ~~^~~~~~~~~~
paint.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         bool add = j + 1 < c.size();
      |                    ~~~~~~^~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:71:11: warning: unused variable 'j' [-Wunused-variable]
   71 |     int i,j;
      |           ^

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