Submission #618899

#	Time	Username	Problem	Language	Result	Execution time	Memory
618899		Dremix10	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2 ms	1236 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;
vector<int> prefw;

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

int cnt(int l, int r){
    if(l == 0)return prefw[r];
    return prefw[r] - prefw[l-1];
}

bool solve(int i, int j, int rem){
    p2(i,j)
    if(i == arr.size()){
        assert(j == c.size() && rem == 0);
        return true;
    }
    if(vis[i][j][rem])return dp[i][j][rem];
    bool res = false;

    if(arr[i] == 2 || arr[i] == 1){
        if(j < c.size()){
            bool ok = true;

            if(cnt(i,i+c[j]-1) > 0)
                ok = false;
            
            if(arr[i+c[j]] == 1)
                ok = false;

            bool add = j + 1 < c.size();

            bool p = false;
            if(ok)
                p = solve(i+c[j]+add,j+1,rem);

            if(p){
                for(int k=0;k<c[j];k++)
                    v[i+k][1] = true;
                if(add)
                    v[i+c[j]][0] = true;
            }
            res |= p;
        }
    }

    if(arr[i] == 2 || arr[i] == 0){
        if(rem > 0){
            bool p = solve(i+1,j,rem-1);
            if(p){
                v[i][0] = true;
            }
            res |= p;
        }
    }
    dp[i][j][rem] = res;
    vis[i][j][rem] = true;
    return res;
}

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;
        }
    }

    prefw.resize(n);
    prefw[0] = arr[0] == 0;
    for(i=1;i<n;i++){
        prefw[i] = prefw[i-1] + (arr[i] == 0);
    }
    pv(arr)
    pv(prefw)

    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));

    assert(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 'bool solve(int, int, int)':
paint.cpp:44:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if(i == arr.size()){
      |        ~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from paint.cpp:2:
paint.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         assert(j == c.size() && rem == 0);
      |                ~~^~~~~~~~~~~
paint.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if(j < c.size()){
      |            ~~^~~~~~~~~~
paint.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             bool add = j + 1 < c.size();
      |                        ~~~~~~^~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:100:11: warning: unused variable 'j' [-Wunused-variable]
  100 |     int i,j;
      |           ^

• 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