Submission #773549

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
773549	2023-07-05 06:40:09	neonaht	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	340 KiB

paint

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
const int S_MAX_LEN = 200 * 1000 + 5;
int qs_[S_MAX_LEN], qsX[S_MAX_LEN], most_left[S_MAX_LEN], most_right[S_MAX_LEN], dpL[S_MAX_LEN][102], dpR[S_MAX_LEN][102];
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int sz = s.size(), k = c.size(), now = 0;
    string res = "";
    s = "_" + s + "_";
    for(int i=1; i<=sz+1; i++) {
        qs_[i] += qs_[i-1] + (s[i] == '_');
        qsX[i] += qsX[i-1] + (s[i] == 'X');
    }
    for(int i=1; i<=sz; i++) {
        if(s[i] == 'X' && now == 0) now = i;
        else if(s[i] != 'X') now = 0;
        most_left[i] = now;
    }
    now = 0;
    for(int i=sz; i>=1; i--) {
        if(s[i] == 'X' && now == 0) now = i;
        else if(s[i] != 'X') now = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• 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