oj.uz

Submission #301384

# Submission time Handle Problem Language Result Execution time Memory
301384 2020-09-17T21:44:42 Z c4ts0up Paint By Numbers (IOI16_paint) C++17
7 / 100
 1 ms 256 KB 
// 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB n = 13, m = 1
2 Correct 0 ms 256 KB n = 18, m = 1
3 Correct 1 ms 256 KB n = 17, m = 1
4 Correct 0 ms 256 KB n = 1, m = 1
5 Correct 0 ms 256 KB n = 20, m = 1
6 Correct 0 ms 256 KB n = 20, m = 1
7 Correct 0 ms 256 KB n = 20, m = 1

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB n = 13, m = 1
2 Correct 0 ms 256 KB n = 18, m = 1
3 Correct 1 ms 256 KB n = 17, m = 1
4 Correct 0 ms 256 KB n = 1, m = 1
5 Correct 0 ms 256 KB n = 20, m = 1
6 Correct 0 ms 256 KB n = 20, m = 1
7 Correct 0 ms 256 KB n = 20, m = 1
8 Incorrect 0 ms 256 KB char #5 differ - expected: 'X', found: '?'
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB n = 13, m = 1
2 Correct 0 ms 256 KB n = 18, m = 1
3 Correct 1 ms 256 KB n = 17, m = 1
4 Correct 0 ms 256 KB n = 1, m = 1
5 Correct 0 ms 256 KB n = 20, m = 1
6 Correct 0 ms 256 KB n = 20, m = 1
7 Correct 0 ms 256 KB n = 20, m = 1
8 Incorrect 0 ms 256 KB char #5 differ - expected: 'X', found: '?'
9 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB n = 13, m = 1
2 Correct 0 ms 256 KB n = 18, m = 1
3 Correct 1 ms 256 KB n = 17, m = 1
4 Correct 0 ms 256 KB n = 1, m = 1
5 Correct 0 ms 256 KB n = 20, m = 1
6 Correct 0 ms 256 KB n = 20, m = 1
7 Correct 0 ms 256 KB n = 20, m = 1
8 Incorrect 0 ms 256 KB char #5 differ - expected: 'X', found: '?'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB n = 13, m = 1
2 Correct 0 ms 256 KB n = 18, m = 1
3 Correct 1 ms 256 KB n = 17, m = 1
4 Correct 0 ms 256 KB n = 1, m = 1
5 Correct 0 ms 256 KB n = 20, m = 1
6 Correct 0 ms 256 KB n = 20, m = 1
7 Correct 0 ms 256 KB n = 20, m = 1
8 Incorrect 0 ms 256 KB char #5 differ - expected: 'X', found: '?'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB n = 13, m = 1
2 Correct 0 ms 256 KB n = 18, m = 1
3 Correct 1 ms 256 KB n = 17, m = 1
4 Correct 0 ms 256 KB n = 1, m = 1
5 Correct 0 ms 256 KB n = 20, m = 1
6 Correct 0 ms 256 KB n = 20, m = 1
7 Correct 0 ms 256 KB n = 20, m = 1
8 Incorrect 0 ms 256 KB char #5 differ - expected: 'X', found: '?'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB n = 13, m = 1
2 Correct 0 ms 256 KB n = 18, m = 1
3 Correct 1 ms 256 KB n = 17, m = 1
4 Correct 0 ms 256 KB n = 1, m = 1
5 Correct 0 ms 256 KB n = 20, m = 1
6 Correct 0 ms 256 KB n = 20, m = 1
7 Correct 0 ms 256 KB n = 20, m = 1
8 Incorrect 0 ms 256 KB char #5 differ - expected: 'X', found: '?'
9 Halted 0 ms 0 KB -