Submission #479442

#	Time	Username	Problem	Language	Result	Execution time	Memory
479442		ponytail	Paint By Numbers (IOI16_paint)	C++17	7 / 100	2 ms	304 KiB

paint

#include "paint.h"

#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <bits/stdc++.h>



using namespace std;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int k = c.size();
    int n = s.size();
    int ps[2][n]; // X _
    ps[0][0] = (s[0] == 'X');
    ps[1][0] = (s[0] == '_');
    for(int i=1; i<n; i++) {
        ps[0][i] = ps[0][i-1] + (s[i] == 'X');
        ps[1][i] = ps[1][i-1] + (s[i] == '_');
    }
    int can[2][n]; // X _
    for(int i=0; i<2; i++) {
        for(int j=0; j<n; j++) {
            can[i][j] = 0;
        }
    }
    if(k == 1) {
        int ok[n] = {};
        for(int i=c[0]-1; i<n; i++) {
            if(ps[1][i] - (i == c[0] - 1 ? 0 : ps[1][i - c[0]]) == 0) {
                if(i == c[0] - 1 || ps[0][i - c[0]] == 0) {
                    if(ps[0][n-1] - ps[0][i] == 0) {
                        ok[i] = 1;
                    }
                }
            }
        }
        for(int i=1; i<n; i++) ok[i] += ok[i-1];
        for(int i=0; i<n; i++) {
            can[0][i] = ok[min(n-1, i + c[0] - 1)] - (i > 0 ? ok[i-1] : 0);
            can[1][i] = (i > 0 && ok[i-1] > 0) || (i + c[0] < n && ok[n-1] - ok[i + c[0] - 1] > 0);
        }
    }
    else {
        int dp[k][n];
    }
    string ans;
    for(int i=0; i<n; i++) {
        if(can[0][i] && can[1][i]) ans += "?";
        else if(can[0][i]) ans += "X";
        else ans += "_";
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:49:13: warning: unused variable 'dp' [-Wunused-variable]
   49 |         int dp[k][n];
      |             ^~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10