Cottarelle in classe

L’ultima idea a cui avevo pensato e speravo funzionasse era di ordinare gli archi e prendere quelli che occupassero meno “spazio” (cioè con differenza assoluta tra m ed f minore possibile), era greedy ma ottengo quasi tutti output non corretti e qualche timeout.

Ho bisogno di qualche hint, non ho idee :confused:

1 Mi Piace

Seguo
Secondo voi funziona in nlogn?
In particolare quante istruzioni al secondo esegue questo server?

Si funziona (e teoricamente non è migliorabile), però questo task ha un input molto grande e senza fast input temo che ti serva un’implementazione molto attenta!

Per il fast input : Fast I/O

1 Mi Piace

Per usare il fastInput con la funzione citata

Dovrei, dopo avere dichiarato la funzione, sostituire per esempio
int n,a;
in>>n;
for(int i=0;i<n;i++)
in>>a;

Con:
int n,a,b;
in>>n;
for(int i=0;i<n;i++)
a=getchar_unlocked();

E basta?

In questo modo stai leggendo un solo carattere, quello che dovresti fare è

a = fast_read_int();
1 Mi Piace

Ho cercato di risolverlo con la LIS (considerando ogni cotta come un intervallo [m, f]) però faccio 0/0 e non capisco dov’è l’errore :confused:
Qualche aiuto?

https://pastebin.com/Crqh976P

1 Mi Piace

Ma se in corsa mattutina io sostituisco

 for (int i = 0; i < M; i++)
 {
    int u,v,w;
    in >> u >> v >> w;

con

 for (int i = 0; i < M; i++)
 {
 int u,v,w;
 u=fast_read_int();
 v=fast_read_int();
 w=fast_read_int();

Ottengo 0/100 con solo timeOut

In corsa mattutina devi leggere da file.
La funzione getchar_unlocked() legge da tastiera.

2 Mi Piace

Un modo semplice per leggere da file usando getchar_unlocked è chiamare freopen all’inizio dell’esecuzione:

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
2 Mi Piace

Riusciresti a elencarmi la sintassi completa dell input/output (le varie istruziono per in e ou)perché solitamente uso la libreria fstream.
Grazie mille!!

Dovrebbe bastare una cosa così:

int fastread()
{
	int N = 0;
	char C = getchar();
	while(C>47 && C<58)
	{
		N = (N<<1) + (N<<3) + C - 48;
		C = getchar();
	}
	return N;
}

int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	int K = fastread();
	cout << K;
	return 0;
}

All’istruzione freopen("input.txt","r",stdin);
crea questo errore

footing.cpp:87:18: error: 'fast_read_int' was not declared in this scope
  N=fast_read_int();

La compilazione dà esito positivo?
Se fallisce prova a postare il codice che trovo un po’ difficile capire qual è la causa senza vederlo.

No okk ho risolto, la compilazione falliva ma per un altro errore, correggendo quello è risultata corretta, grazie mille.

#include <cstdio>

int readInt()
{
    int res = 0;
    char ch = 0;
    while(ch < '0') ch = getchar_unlocked();
    for(; ch >= '0'; ch = getchar_unlocked()) res = res * 10 + ch - '0';
    return res;
}

void writeInt(int v)
{
    char buf[14];
    int p = 0;
    if(v == 0) buf[p++] = 0;
    for(; v; v /= 10) buf[p++] = v % 10;
    while(p--) putchar_unlocked(buf[p] + '0');
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    int N = readInt();
    writeInt(N);
}

Occhio che tutte le funzioni postate finora non gestiscono i numeri negativi

1 Mi Piace

Nel caso in cui ho in input sia int che char posso alternare la funzione readInt() con getchar_unlocked() per i caratteri? :slight_smile:

Credo di si, quando invece hai delle stringhe è sufficiente usare push_back.
Fai però attenzione al tipo di caratteri e ai controlli che devi fare, per esempio quando ti dice che sono presenti solo caratteri stampabili.

Se l’input è del tipo intero [spazio] carattere allora devi stare attento a non considerare lo spazio come il carattere che cerchi. Quello che di solito faccio è questo:

int N = readInt();
char ch = '\0';
while(ch <= ' ') ch = getchar_unlocked();
1 Mi Piace

Riapro la questione dopo mesi
Per andare a capo dopo l’output?
Chiedo perché in locale non mi fa usare la getchar_unlocked ()

1 Mi Piace

Se non sbaglio funziona solo con linux