Submission #1192288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192288		meisgood	Paint By Numbers (IOI16_paint)	C++20	59 / 100	249 ms	484336 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std ;
#include <cstdlib>
bool dp[200003][103] ;
pair<int,int> lst[200003][103] ;
int n,k ;
string s ;
vector <int> c ;
int psw[200003],psb[200003] ;
vector <pair<int,int>> adj[200003][103] ;
void dfs(int x,int y){
    if (y>k) return ;
    if (dp[x][y]) return ;
    dp[x][y]=1 ;
    // cout << x << " " << y << endl ;
    if (x<=n){
        if ((x+1>n||s[x+1]!='X')&&s[x]!='X'){
            dfs(x+1,y) ;
            // lst[x+1][y]={x,y} ;
            adj[x+1][y].push_back({x,y}) ;
        }
    }
    if (x+c[y]<=n){
        if (psw[x+c[y]]-psw[x]==0){
            dfs(x+c[y]+1,y+1) ;
            // lst[x+c[y]+1][y+1]={x,y} ;
            adj[x+c[y]+1][y+1].push_back({x,y}) ;
        }
    }
}
int www[200003],bbb[200003] ;
bool vvv[200003][103] ;
void dfs2(int x,int y){
    if (vvv[x][y]) return ;
    vvv[x][y]=1 ;
    for (auto [a,b] : adj[x][y]){
        // cout << x << " " << y << " " << a << " " << b << endl ;
        if (y!=b){
            bbb[a+1]++ ;
            bbb[x]-- ;
            www[a]++ ;
            www[a+1]-- ;
            www[x]++ ;
            www[x+1]-- ;
        }
        else {
            www[a]++ ;
            www[a+1]-- ;
        }
        dfs2(a,b) ;
    }
}
std::string solve_puzzle(std::string ss, std::vector<int> cc) {
    int i,j ;
    ss='0'+ss ;
    s=ss,c=cc ;
    n=s.size()-1 ;
    k=cc.size() ;
    for (i = 1 ; i <= n ; i ++) psw[i]=psw[i-1]+(s[i]=='_') ;
    for (i = 1 ; i <= n ; i ++) psb[i]=psb[i-1]+(s[i]=='X') ;
    dfs(0,0) ;
    dfs2(n+1,k) ;
    // int x=n+1,y=k ;
    // string sss="" ;
    // for (i = 0 ; i < n ; i ++) sss+='_' ;
    // vector <pair<int,int>> v ;
    // while (1){
    //     auto [a,b]=lst[x][y] ;
    //     x=a,y=b ;
    //     cout << x << " " << y << endl ;
    //     v.push_back({x,y}) ;
    //     if (x==0&&y==0) break ;
    // }
    // for (i = 0 ; i < v.size()-1 ; i ++){
    //     if (v[i].second!=v[i+1].second){
    //         for (j = v[i+1].first ; j < v[i].first-1 ; j ++) sss[j]='X' ;
    //     }
    // }
    string sss="" ;
    int tt=0,tt2=0 ;
    for (i = 0 ; i <= n ; i ++){
        tt+=www[i] ;
        tt2+=bbb[i] ;
        // cout << tt << " " << tt2 << endl ;
        if (i!=0){
            // if (s[i]!='.') sss+=s[i] ;
            // else 
            if (tt&&tt2) sss+='?' ;
            else if (!tt&&!tt2) sss+='?' ;
            else if (!tt) sss+='X' ;
            else sss+='_' ;
        }
    }
    return sss;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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