oj.uz

답안 #200989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200989 2020-02-09T04:08:08 Z AQT Paint By Numbers (IOI16_paint) C++14
0 / 100
 5 ms 376 KB 
#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

long long pre[2][200005];
bool dp[2][105][200005];
int par[2][105][200005];

string solve_puzzle(string s, vector<int> c){
    int N = s.size(), K = c.size();
    for(int i = 1; i<=N; i++){
        if(s[i-1] == '_'){
            pre[0][i] = 1;
        }
        else if(s[i-1] == 'X'){
            pre[1][i] = 1;
        }
        pre[0][i] += pre[0][i-1];
        pre[1][i] += pre[1][i-1];
    }
    dp[0][0][0] = 1;
    for(int k = 0; k<=K; k++){
        for(int i= 0; i<=N; i++){
            for(int b = 0; b<2; b++){
                if(dp[b][k][i]){
                    if(s[i] != 'X'){
                        par[0][k][i+1] = -b;
                        dp[0][k][i+1] = 1;
                    }
                    if(k != K && c[k] + i <= N && pre[0][c[k]+i]-pre[0][i] == 0){
                        par[1][k+1][i+c[k]] = 1;
                        dp[1][k+1][i+c[k]] = 1;
                    }
                }
            }
        }
    }
    string ret;
    int crntb = 0, crntk = K, crntn = N;
    if(dp[1][K][N]){
        crntb = 1;
    }
    while(crntn){
        if(par[crntb][crntk][crntn] == 1){
            int lim = crntn - c[crntk-1];
            while(crntn > lim){
                ret.push_back('X');
                crntn--;
            }
            crntk--;
            crntb ^= 1;
        }
        else if(par[crntb][crntk][crntn] == -1){
            crntb ^= 1;
            crntn--;
            ret.push_back('_');
        }
        else{
            ret.push_back('_');
            crntn--;
        }
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

/*
int main(){
    cout << solve_puzzle("..........", {3, 4}) << endl;
}
*/

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -