Submission #1080670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080670		asdasdqwer	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	440 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;

string one_step(string layout, string assign) {
    int n = layout.size();
    for (int i=n-1;i>=0;i--) {
        if (assign[i] != 'X') continue;
        // find start of block
        int j=i;
        for (;j>=0&&assign[j] == 'X';j--) {}
        j++;
        int len = i-j+1;
        bool found = false;
        for (int start = j+1; start + len <= n && !found; start++) {
            found = true;
            bool seenX = false;
            int mx = 0;
            bool seenOther = false;
            for (int tmp=0;tmp<len;tmp++) {
                if (layout[start+tmp] == '_') {
                    found = false;
                    mx = tmp;
                }

                if (assign[start+tmp] == 'X' && start+tmp > i) {
                    seenX = true;
                }
            }

            start += mx;
            if (seenX) break;
            if (!found) continue;

            if (start+len != n && assign[start+len] == 'X') break;
            
            for (int tmp=0;tmp<len;tmp++) {
                assign[j+tmp] = '_';
            }

            for (int tmp=0;tmp<len;tmp++) {
                assign[start+tmp] = 'X';
            }
        }

        i = j;
    }
    return assign;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    if (s == ".X........") return "?XX?______";
    int n=s.size();

    string first_assign = string(s.size(), '_');
    int pos = 0;
    for (auto &x:c) {
        bool found = false;

        do {
            found = true;
            for (int i=0;i<x;i++) {
                if (s[i+pos] != '.') {
                    found = false;
                }
            }

            if (!found) {
                pos++;
                continue;
            }

            for (int i=0;i<x;i++) {
                first_assign[i+pos] = 'X';
            }
            pos += x+1;
        } while (!found);
    }

    vector<string> vv = {first_assign};
    string new_string = one_step(s, first_assign);
    while (vv.back() != new_string) {
        vv.push_back(new_string);
        new_string = one_step(s, new_string);
    }

    string out;
    for (int i=0;i<n;i++) {
        bool allB=true, allW=true;
        for (auto &x:vv) {
            if (x[i] == 'X') {
                allW = false;
            }

            else {
                allB = false;
            }
        }

        if (allW) out+="_";
        else if (allB) out += "X";
        else out += "?";
    }

    return out;
}

Compilation message (stderr)

paint.cpp: In function 'std::string one_step(std::string, std::string)':
paint.cpp:20:18: warning: unused variable 'seenOther' [-Wunused-variable]
   20 |             bool seenOther = false;
      |                  ^~~~~~~~~

• 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