Submission #239855

#	Time	Username	Problem	Language	Result	Execution time	Memory
239855		nicolaalexandra	Paint By Numbers (IOI16_paint)	C++14	59 / 100	5 ms	512 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
#define DIM 100010
#define DIMK 110
using namespace std;

int sp[DIM],sp2[DIM],Left[DIM],Right[DIM],aib[DIM],dp_left[DIM][DIMK],dp_right[DIM][DIMK];

int get_sum (int x, int y){
    if (x > y)
        return 0;
    int sol = sp[y];
    if (x)
        sol -= sp[x-1];
    return sol;
}

int get_sum2 (int x, int y){
    if (x > y)
        return 0;
    int sol = sp2[y];
    if (x)
        sol -= sp2[x-1];
    return sol;
}

void update (int p, int n, int val){
    for (;p<=n;p+=(p&-p))
        aib[p] += val;
}

int query (int p){
    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}

string solve_puzzle (string s, vector <int> c){

    int n = s.length(), i, j;

    for (i=0;i<n;i++){
        sp[i] = i ? sp[i-1] : 0;
        sp2[i] = i ? sp2[i-1] : 0;
        if (s[i] == '_')
            sp[i]++;
        if (s[i] == 'X')
            sp2[i]++;
    }

    /// dp_left[i][j] = true daca pot sa pun primele j piese pe primele i pozitii\
    si piesa j sa se termine fix pe i

    for (j=0;j<c.size();j++){
        int lg = c[j];

        for (i=lg-1;i<n;i++){
            if (get_sum(i-lg+1,i))
                continue;
            if (!j){
                if (get_sum2(0,i-lg) == 0)
                    dp_left[i][j] = 1;
                continue;
            }

            int poz = i-lg-1;
            while (poz >= 0 && dp_left[poz][j-1] == 0) /// o sa optimizez asta mai tarziu
                poz--;

            if (poz < 0)
                continue;

            if (get_sum2(poz+1,i-lg) == 0) /// sa nu am X in intervalul care ramane liber
                dp_left[i][j] = 1;

        }}

    for (j=c.size()-1;j>=0;j--){
        int lg = c[j];
        for (i=n-lg;i>=0;i--){
            if (get_sum(i,i+lg-1))
                continue;
            if (j == c.size()-1){
                if (get_sum2 (i+lg,n-1) == 0)
                    dp_right[i][j] = 1;
                continue;
            }

            int poz = i + lg + 1;
            while (poz < n && dp_right[poz][j+1] == 0)
                poz++;

            if (poz >= n)
                continue;

            if (get_sum2(i+lg,poz-1) == 0)
                dp_right[i][j] = 1;
        }}



    for (j=0;j<c.size();j++){

        /// intersectia tuturor intervalelor in care poate fi pusa piesa

        int st = -1, dr = -1, lg = c[j];
        for (i=0;i<n;i++){
            if (!dp_left[i][j] || !dp_right[i-lg+1][j])
                continue;
            if (st == -1)
                st = i-lg+1, dr = i;
            else st = i-lg+1;

            update (i-lg+1 +1,n+1,1);
            update (i+1 +1,n+1,-1);
        }

        if (st <= dr){
            for (i=st;i<=dr;i++)
                s[i] = 'X';
        }

    }


    for (i=0;i<n;i++){
        if (s[i] == '.' && query(i+1) == 0)
            s[i] = '_';
        else {
            if (s[i] == '.')
                s[i] = '?';
        }
    }

    return s;

}

Compilation message (stderr)

paint.cpp:52:5: warning: multi-line comment [-Wcomment]
     /// dp_left[i][j] = true daca pot sa pun primele j piese pe primele i pozitii\
     ^
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j=0;j<c.size();j++){
              ~^~~~~~~~~
paint.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j == c.size()-1){
                 ~~^~~~~~~~~~~~~
paint.cpp:103:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j=0;j<c.size();j++){
              ~^~~~~~~~~

• 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