Submission #1245063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245063		matisito	Paint By Numbers (IOI16_paint)	C++20	59 / 100	0 ms	328 KiB

paint

#include "paint.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <cstdlib>

using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";

/*  
I love VN uwu
*/

string solve_puzzle(string s, vector<int> c){
    int n=(int)c.size();
    vector<int>pref;
    pref.push_back(0);
    for(char ch:s){
        if(ch=='.') pref.push_back(pref.back()+1);
        else pref.push_back(pref.back());
    }
    vector<int>start(n), end(n);
    // dbg((int)pref.size());
    int l=0, r;
    for(int i=0 ; i<n ; i++){
        // dbg(i)
        for(int j=l ; j<(int)s.size() ; j++){
            r=j+c[i]-1;
            // dbg(pref[r+1])
            // dbg(pref[j])
            if(pref[r+1]-pref[j]==r-j+1){
                start[i]=j;
                l=r+2;
                break;
            }
        }
    }
    r=(int)s.size()-1;
    for(int i=n-1 ; i>=0 ; i--){
        for(int j=r ; j>=0 ; j--){
            l=j-c[i]+1;
            if(pref[j+1]-pref[l]==j-l+1){
                end[i]=l;
                r=l-2;
                break;
            }
        }
    }
    vector<int>auxi((int)s.size());
    int maxi=0, valenotta=0;
    for(int i=0 ; i<n ; i++){
        // dbg(start[i])
        // dbg(end[i])
        for(int j=start[i] ; j<=end[i] ; j++){
            l=j; r=j+c[i]-1;
            if(pref[r+1]-pref[j]<r-l+1) continue;
            valenotta=end[i]-start[i]+1;
            // if(start[i]==end[i]){
            //     for(int k=0 ; k<(int)s.size() ; k++){
            //         if(k>=l && k<=r){
            //             auxi[k]=1e9;
            //         }
            //         // else auxi[k].insert('_');
            //     }
            //     continue;
            // }
            for(int k=0 ; k<(int)s.size() ; k++){
                if(k>=l && k<=r){
                    auxi[k]++;
                    if(auxi[k]>=valenotta) auxi[k]=1e9;
                }
                // else auxi[k].insert('_');
            }
        }
        // maxi=max(maxi, valenotta);
        // valenotta=0;
    }
    // for(int x:auxi) dbg(x)
    string ans;
    for(int i=0 ; i<(int)s.size() ; i++){
        if(auxi[i]>=1e9) ans+='X';
        else if(auxi[i]==0) ans+='_';
        else ans+='?';
    }
    return ans;
}

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