Submission #333088

#	Time	Username	Problem	Language	Result	Execution time	Memory
333088		MarcoMeijer	Paint By Numbers (IOI16_paint)	C++14	59 / 100	139 ms	179948 KiB

paint

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second

const int MX=2e5+10;

int n, k;
vi c;
int sm[MX][101];
int possible[MX][101];
int smX[MX], sm_[MX];
bool visited[MX][101];

int getSum(int x, int y, char c) {
    return sm[min(n,y+1)][c]-sm[x][c];
}
void addX(int x, int y) {
    smX[y+1]--;
    smX[x]++;
}
void add_(int x, int y) {
    sm_[y+1]--;
    sm_[x]++;
}
bool isPossible(int x, int y) {
    if(x >= n) {
        return y == k;
    }
    if(possible[x][y] != -1) return possible[x][y];

    bool res = isPossible(x+1,y);

    if(y == k) {
        if(getSum(x,x,'X') == 1)
            res = 0;
    } else {
        if(x+c[y] <= n && getSum(x,x+c[y]-1,'_') == 0 && getSum(x+c[y],x+c[y],'X') == 0) {
            if(isPossible(x+c[y]+1,y+1))
                res = 1;
        } else if(getSum(x,x,'X') == 1) {
            res = 0;
        }
    }

    return possible[x][y] = res;
}
void visit(int x, int y) {
    if(visited[x][y])
        return;
    if(x >= n) return;
    visited[x][y] = 1;
    if(!isPossible(x,y))
        return;
    
    if(y == k) {
        add_(x,x);
        visit(x+1,y);
    } else {
        if(x+c[y] <= n && getSum(x,x+c[y]-1,'_') == 0 && getSum(x+c[y],x+c[y],'X') == 0) {
            if(isPossible(x+c[y]+1,y+1)) {
                addX(x,x+c[y]-1);
                add_(x+c[y],x+c[y]);
                visit(x+c[y]+1,y+1);
            }
        }
        if(getSum(x,x,'X') == 0 && isPossible(x+1,y)) {
            add_(x,x);
            visit(x+1,y);
        }
    }
}

string solve_puzzle(string s, vi C) {
    c=C;
    n = s.size(); k = c.size();
    RE(i,MX) RE(j,101) sm[i][j] = 0;
    RE(i,n) RE(j,101) sm[i+1][j] = sm[i][j]+(s[i]==j?1:0);
    RE(i,MX) RE(j,101) possible[i][j] = -1;
    RE(i,MX) smX[i]=sm_[i]=0;
    RE(i,MX) RE(j,101) visited[i][j] = 0;
    visit(0,0);
    REP(i,1,MX) smX[i]+=smX[i-1];
    REP(i,1,MX) sm_[i]+=sm_[i-1];
    string ans;
    RE(i,n) {
        if(smX[i] && sm_[i]) {
            ans.push_back('?');
        } else if(smX[i]) {
            ans.push_back('X');
        } else {
            ans.push_back('_');
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int getSum(int, int, char)':
paint.cpp:35:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |     return sm[min(n,y+1)][c]-sm[x][c];
      |                           ^
paint.cpp:35:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |     return sm[min(n,y+1)][c]-sm[x][c];
      |                                    ^
paint.cpp: In function 'bool isPossible(int, int)':
paint.cpp:65:27: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   65 |     return possible[x][y] = res;
      |            ~~~~~~~~~~~~~~~^~~~~

• 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