Submission #427446

#	Time	Username	Problem	Language	Result	Execution time	Memory
427446		InternetPerson10	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	204 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;

int sol[200001], check[200001], answ[200001], pos1[101], pos2[101];
vector<int> clue;

bool chec(int x, int y) {
    for(int i = x; i < y; i++) {
        if(sol[i]) return false;
    }
    return true;
}

void redo(int n) {
    for(int i = 0; i < n; i++) {
        if(answ[i] == 1) {
            if(check[i] == 0) answ[i] = 2;
        }
        if(answ[i] == 0) {
            if(check[i] == 1) answ[i] = 2;
        }
    }
}

string solve_puzzle(string s, vector<int> c) {
    clue.swap(c);
    int n = s.size();
    int x = 0;
    for(int i = 0; i < n; i++) {
        if(s.at(i) == '_') {
            sol[i] = 1;
        }
        if(s.at(i) == 'X') {
            sol[i] = 2;
        }
        if(s.at(i) == '.') {
            sol[i] = 0;
        }
    }
    for(int i = 0; i < clue.size(); i++) {
        for(int j = x; j < n; j++) {
            if(chec(j, j + clue[i])) {
                pos1[i] = j;
                x = j + clue[i] + 1;
                break;
            }
        }
    }
    reverse(clue.begin(), clue.end());
    reverse(sol, sol+n);
    x = 0;
    for(int i = 0; i < clue.size(); i++) {
        for(int j = x; j < n; j++) {
            if(chec(j, j + clue[i])) {
                pos2[clue.size() - 1 - i] = (n-1) - (j + clue[i] - 1);
                x = j + clue[i] + 1;
                break;
            }
        }
    }
    reverse(clue.begin(), clue.end());
    reverse(sol, sol+n);
    for(int i = 0; i < clue.size(); i++) {
        for(int j = pos1[i]; j < pos1[i] + clue[i]; j++) {
            answ[j] = 1;
            check[j] = 1;
        }
    }
    // for(int l = 0; l < n; l++) cout << check[l];
    // cout << '\n';
    for(int i = clue.size()-1; i >= 0; i--) {
        int k = pos1[i];
        for(int j = pos1[i]; j <= pos2[i]; j++) {
            if(chec(j, j + clue[i])) {
                // cout << j << " good\n";
                for(int l = k; l < k + clue[i]; l++) check[l] = 0;
                k = j;
                for(int l = k; l < k + clue[i]; l++) check[l] = 1;
                // for(int l = 0; l < n; l++) cout << check[l];
                // cout << '\n';
                redo(n);
            }
        }
    }
    string ans;
    ans.resize(n);
    // for(int i = 0; i < n; i++) cout << check[i];
    // cout << '\n';
    for(int i = 0; i < n; i++) {
        if(answ[i] == 0) ans[i] = '_';
        if(answ[i] == 1) ans[i] = 'X';
        if(answ[i] == 2) ans[i] = '?';
        // if()
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0; i < clue.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
paint.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0; i < clue.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
paint.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0; i < clue.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

• 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