제출 #333277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333277		MarcoMeijer	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1394 ms	355308 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][200];
int possible[MX][200];
int smX[MX], sm_[MX];
bool visited[MX][200];

inline int getSum(int x, int y, int c) {
    return sm[min(n,y+1)][c]-sm[x][c];
}
inline void addX(int x, int y) {
    smX[y+1]--;
    smX[x]++;
}
inline void add_(int x, int y) {
    sm_[y+1]--;
    sm_[x]++;
}
inline bool isPossible(int x, int y) {
    if(x >= n) return y == k;
    return possible[x][y];
}
void visit(int x, int y) {
    if(x >= n) return;
    if(visited[x][y])
        return;
    visited[x][y] = 1;
    if(!possible[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,200) sm[i][j] = 0;
    RE(i,n) sm[i+1]['_'] = sm[i]['_']+(s[i]=='_'?1:0);
    RE(i,n) sm[i+1]['X'] = sm[i]['X']+(s[i]=='X'?1:0);
    RE(i,n) sm[i+1]['.'] = sm[i]['.']+(s[i]=='.'?1:0);
    RE(i,MX) smX[i]=sm_[i]=0;

    REV(x,0,n) RE(y,k+1) {
        possible[x][y] = 0;
        if(getSum(x,x,'X') == 0)
            if(isPossible(x+1,y))
                possible[x][y] = 1;

        if(y != k)
            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))
                    possible[x][y] = 1;
    }

    RE(i,n+1) RE(j,k+1) 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; ans.resize(n);
    RE(i,n) {
        if(smX[i] && sm_[i]) {
            ans[i] = '?';
        } else if(smX[i]) {
            ans[i] = 'X';
        } else {
            ans[i] = '_';
        }
    }
    return ans;
}

• 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