Submission #301384

#	Time	Username	Problem	Language	Result	Execution time	Memory
301384		c4ts0up	Paint By Numbers (IOI16_paint)	C++17	7 / 100	1 ms	256 KiB

paint

// c4ts0up
// Alvaro Bacca - COL3

#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;

int n, k;
vector <int> ps;
string cad = "";

// encuentra la interseccion de [a] union [b]. devuelve {-1,-1} si no hay
pair <int,int> interseccion(pair <int,int> a, pair <int,int> b) {
    pair <int,int> res = {b.ff, a.ss};
    if (b.ff > a.ss) return {-1,-1};
    else return res;
}

string solve_puzzle(string s, vector<int> c) {
    n = c.size();
    k = s.size();
    for (int i=0; i<k; i++) cad += "?";

    // calculamos el prefix sum de derecha a izquierda
    ps.resize(n);
    ps[n-1] = 0;
    for (int i=n-2; i>=0; i--) {
        ps[i] = ps[i+1] + c[i+1] + 1;
    }

    /*//
    cout << "ps := ";
    for (int x : ps) cout << x << " ";
    cout << endl;
    //*/

    // recorremos el arreglo
    int prev = 0;
    for (int i=0; i<n; i++) {
        pair <int,int> p1 = {k-ps[i]-(c[i]-1)-1, k-ps[i]-1};
        pair <int,int> p2 = {prev, prev+c[i]-1};

        /*//
        cout << "p1 := " << p1.ff << " " << p1.ss << endl;
        cout << "p2 := " << p2.ff << " " << p2.ss << endl;
        //*/

        pair <int,int> inter = interseccion(p2,p1);

        if (inter.ff == -1) continue;
        else {
            for (int j=inter.ff; j<=inter.ss; j++) cad[j] = 'X';
        }

        prev += c[i]+1;
    }

    // quitamos las preguntas que quedan
    for (int i=1; i<k-1; i++) {
        if (cad[i] == '?' && cad[i-1] == 'X' && cad[i+1] == 'X') cad[i] = '.';
    }

    return cad;
}

• 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