Ois_ruspa 70 / 100

Aiuto
1

Salve a tutti,
Sto provando da ieri sera a risolvere il problema “SmartRuspa (ruspa)” e ottengo il 70/100 per via dell’ultimo test dell’ultimo subtask che va in “Execution Timed Out”
Qui trovate il mio codice : https://pastebin.com/YiARUPCw
Grazie.

2

La tua soluzione ha complessità O(N+T) ed è strano che vada fuori tempo.
Indagando più a fondo ho scoperto che è l’output che rallenta sensibilmente il programma, mi è bastato utilizzare l’I/O del C++ per ottenere 100/100.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <fstream>
#define MAXN 100000
using namespace std;
 
int N, W[2];
vector<int> M;
 
void inizia()
{
    W[0] = M[(N-1)/2];
    W[1] = M[N/2];
}
 
inline bool abbatti(int X, bool D)
{
    return (X<=W[D]);
}
 
int main()
{
    int T, X;
    bool D;
    
    ifstream in("input.txt");
    ofstream out("output.txt");
    
    in >> N >> T;
    for(int i=0; i<N; i++)
    {
        int a;
        in >> a;
        M.push_back(a);
    }
    inizia();
    for(int i=0; i<T; i++)
    {
        in >> X >> D;
        out << abbatti(X,D) << ' ';
    }
    return 0;
}

P.S. le formule non funzionano più?

1 Mi Piace
3

Grazie,
Ma quindi come I/O alle ois cosa conviene usare ?

4

Alle OIS o usi scanf/printf e freopen, oppure usi ifstream/ofstream, oppure usi fscanf/fprintf, oppure infine usi cin/cout e freopen includendo queste due espressioni:

ios_base::sync_with_stdio(false);
cin.tie();

Queste fanno in modo che cin/cout non vengano rallentate dal meccanismo di sincronizzazione con printf/scanf: questo significa che la performance sarà al livello di scanf/printf, ma non potrai più usare entrambe le istruzioni nello stesso programma (o usi tutte cin/cout, o tutte printf/scanf).
Per le OII invece non devi leggere da file quindi il problema non si pone.