제출 #774904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774904		Cookie	Paint By Numbers (IOI16_paint)	C++14	80 / 100	2086 ms	474508 KiB

paint

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(ll i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#include "paint.h"

#include <cstdlib>
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
#define ull unsigned long long
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 1e6 + 5, mxq = 2e5 + 5, sq = 400, mxv = 15 * 10, pr = 31;
const int base = (1 << 18);
const ll inf = 2e9, neg = -69420;
void add(int &a, int b){
    a += b;
    if(a >= mod)a -= mod;
}
int dp[105][105][105];
bool vis[105 * 105 * 105];
vt<int>adj[105 * 105 * 105];
map<pair<pair<int, int>, int>, int>mp;
string s;
int coef(int i, int j, int k){
    return(mp[make_pair(make_pair(i, j), k)]);
}


std::string solve_puzzle(std::string s, std::vector<int> c) {
    s += '_';
    vt<int>a; 
    forr(i, 0, sz(c)){
        a.pb(c[i]);
    }
    
    int cnt = 0;
    dp[0][0][0] = 1; 
    for(int i = 0; i <= sz(s); i++){
        for(int j = 0; j <= sz(a); j++){
            for(int k = 0; k <= a[j]; k++){
                mp[{{i, j}, k}] = ++cnt;
            }
        }
    }
    for(int i = 0; i < sz(s); i++){
        for(int j = 0; j <= sz(a); j++){
            for(int k = 0; k <= a[j]; k++){
                if(dp[i][j][k] == 0)continue;
                if(s[i] == '_' || s[i] == '.'){
                    if(k == 0){
                        add(dp[i + 1][j][0], dp[i][j][k]);
                        adj[coef(i + 1, j, 0)].pb(coef(i, j, k));
                    }else if(j < sz(a) && k == a[j]){
                        add(dp[i + 1][j + 1][0], dp[i][j][k]);
                        adj[coef(i + 1, j + 1, 0)].pb(coef(i, j, k));
                    }
                }if(s[i] == '.' || s[i] == 'X'){
                    if(j < sz(a) && k < a[j]){
                        add(dp[i + 1][j][k + 1], dp[i][j][k]);
                        adj[coef(i + 1, j, k + 1)].pb(coef(i, j, k));
                    }
                }
            }
        }
    }
   
    queue<int>q; q.push(coef(sz(s), sz(a), 0)); vis[coef(sz(s), sz(a), 0)] = 1;
    while(!q.empty()){
        int nw = q.front(); q.pop();
        for(auto i: adj[nw]){
            if(!vis[i]){
                vis[i] = 1;
                q.push(i);
            }
        }
    }
    string res = "";
    for(int i = 0; i < sz(s) - 1; i++){
        bool ok1 = 0, ok2 = 0;
        for(int j = 0; j <= sz(a); j++){
            for(int k = 0; k <= a[j]; k++){
                if(!vis[coef(i, j, k)])continue;
                if(k == 0 && vis[coef(i + 1, j, 0)])ok1 = 1;
                if(j < sz(a) && a[j] == k && vis[coef(i + 1, j + 1, 0)])ok1 = 1;
                if(j < sz(a) && k < a[j] && vis[coef(i + 1, j, k + 1)])ok2 = 1;
            }
        }
        if(ok1 && ok2)res += '?';
        else if(ok1)res += '_';
        else res += 'X';
    }
    return(res);
}

• 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