Submission #550652

#	Time	Username	Problem	Language	Result	Execution time	Memory
550652		LucaDantas	Sparklers (JOI17_sparklers)	C++17	0 / 100	1 ms	212 KiB

sparklers

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

constexpr int maxn = 25, inf = 0x3f3f3f3f;

int x[maxn], n, k, T;
vector<vector<int>> possibilidades;
vector<int> aux;

void brute(int l, int r) {
    if(aux.size() == n) {
        static vector<int> tempo;
        tempo.clear(); tempo.resize(n);
        for(int i = 0; i < n; i++)
            tempo[aux[i]] = i+1; // 1-indexed, no need to add 1 when considering it later
        tempo[aux[n-1]] = n-1;
        possibilidades.push_back(tempo);
        return;
    }
    if(l >= 0) {
        aux.push_back(l);
        brute(l-1, r);
        aux.pop_back();
    }
    if(r < n) {
        aux.push_back(r);
        brute(l, r+1);
        aux.pop_back();
    }
}

bool check(int s) {
    for(const vector<int>& ordem : possibilidades) {
        int posL = inf;
        bool bad = 0;
        for(int i = 0; i < k; i++) {
            if(x[i] - posL > 1ll * ordem[i] * T * s)
                { bad = 1; break; } // não dá pra eu chegar no anterior

            posL = (int)min(1ll * posL, x[i] + 1ll * ordem[i] * T * s);
        }
        
        int posR = 0;
        for(int i = k; i < n; i++) {
            if(posR - x[i] > 1ll * ordem[i] * T * s)
                { bad = 1; break; }

            posR = (int)max(1ll * posR, x[i] - 1ll * ordem[i] * T * s);
        }
        
        if(bad) continue;

        if(posL >= posR)
            return 1;
    }
    return 0;
}

int main() {
    scanf("%d %d %d", &n, &k, &T); --k; // 0-indexed
    for(int i = 0; i < n; i++)
        scanf("%d", x+i);
    
    aux.push_back(k);
    brute(k-1, k+1);

    int l = 0, r = inf, ans = -1;
    while(l <= r) {
        int m = (l+r) >> 1;
        if(check(m))
            r = m-1, ans = m;
        else
            l = m+1;
    }

    printf("%d\n", ans);
}

Compilation message (stderr)

sparklers.cpp: In function 'void brute(int, int)':
sparklers.cpp:11:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |     if(aux.size() == n) {
      |        ~~~~~~~~~~~^~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d %d %d", &n, &k, &T); --k; // 0-indexed
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d", x+i);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50