Circular monuments


#1

La mia soluzione con 6 testcase da TLE con la sola lettura dei dati, elaborazione nulla e stampa del numero dei dati letti.
Inoltre, in quei testcase, se leggo (MAX. 1 000 000) di interi con una scanf ho una occupazione di memoria di circa 29MB mentre se li leggo con una funzione specializzata per leggere gli interi l’occupazione di memoria sale a 41MB circa.
Potreste controllare grazie.


#2

Ho sottoposto il seguente codice dove leggo semplicmente i dati di input e non ottengo nessun time out.

#include  <bits/stdc++.h>

using namespace std;

int main(){
	freopen("input.txt","r",stdin);
	int N,K,L;
	scanf("%d%d%d",&N,&K,&L);
	vector <int> v (N);
	for(int i = 0; i < N;i++){
		scanf("%d",&v[i]);
	}
}

Ho fatto varie prove con scanf, fscanf e la libreria fstream e ho ottenuto che con i primi due metodi i casi peggiori sono circa di mezzo secondo mentre con la fstream di 0.360s.
Non ho utilizzato le funzioni .tie(0) e .sync_with_stdio(0) con la fstream.
Memoria massima usata 5.4 MiB


#3

Intendi una funzione che usa getc per leggere carattere per carattere?
Strano, prova magari a postare il sorgente :slightly_smiling_face:

Leggendo con un ifstream e stampando tutti i dati letti, non dovrebbe esserci nessun TLE :grin:


#4

Probabilmente il problema del TLE è dovuto al fatto che vado a mettere quello che leggo dal file in un oggetto map<int,int> (o anche map <int,char>) dove il primo termine è l’angolo (x o x+K) ed il secondo rappresenta la quantità di statue presenti in quelle posizioni (1 o 2) per poi fare una scansione di un massimo di N termini, N/2 nel caso migliore.
Comunque se per leggere gli interi uso una funzione che riporto sotto

int fast_read_int() {
	int c, n = 0;
	do c = getchar_unlocked();
	while (c < '0' || c > '9' );
	do {
		n = (n << 3) + (n << 1) + (c - '0');
		c = getchar_unlocked();
	} while (c >= '0' && c <= '9');
	return n;
}

ad esempio nei test case 3 e 6 oltre al TLE ho una occupazione di memoria fino a 37MB
con la scanf circa 29MB

CODICE CHE OCCUPA PIU’ MEMORIA

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <map>
using namespace std;
map <int,char> statue;
int fast_read_int() {
	int c, n = 0;
	do c = getchar_unlocked();
	while (c < '0' || c > '9' );
	do {
		n = (n << 3) + (n << 1) + (c - '0');
		c = getchar_unlocked();
	} while (c >= '0' && c <= '9');
	return n;
}
int N, K, L;
int main() {
    FILE *fr, *fw;
    int i;
	int posst; // posizione di una statua
    fr =freopen("input.txt","r", stdin);
    fw =freopen("output.txt","w", stdout);
	//fscanf(fr, "%d %d %d", &N, &K, &L);
	N=fast_read_int();
	K=fast_read_int();
	L=fast_read_int();
	if(L==K){
		printf("%d\n",N);
		return 0;
	}
	if(N==2*K){
		printf("%d\n",2*L);
		return 0;
	}
		for(i=0; i<N; i++){
			//fscanf(fr, "%d", &posst);
			posst=fast_read_int();
			if(posst>=K)
				posst-=K;
			statue[posst]++;
		}
	fprintf(fw, "%d\n",N);
    fclose(fr);
    fclose(fw);
    return 0;
}

CODICE CHE OCCUPA MENO MEMORIA

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <map>
using namespace std;
map <int,char> statue;
/*
int fast_read_int() {
	int c, n = 0;
	do c = getchar_unlocked();
	while (c < '0' || c > '9' );
	do {
		n = (n << 3) + (n << 1) + (c - '0');
		c = getchar_unlocked();
	} while (c >= '0' && c <= '9');
	return n;
}
*/
int N, K, L;
int main() {
    FILE *fr, *fw;
    int i;
	int posst; // posizione di una statua
    fr =freopen("input.txt","r", stdin);
    fw =freopen("output.txt","w", stdout);
	fscanf(fr, "%d %d %d", &N, &K, &L);
	/*
	N=fast_read_int();
	K=fast_read_int();
	L=fast_read_int();
	*/
	if(L==K){
		printf("%d\n",N);
		return 0;
	}
	if(N==2*K){
		printf("%d\n",2*L);
		return 0;
	}
		for(i=0; i<N; i++){
			fscanf(fr, "%d", &posst);
			//posst=fast_read_int();
			if(posst>=K)
				posst-=K;
			statue[posst]++;
		}
	fprintf(fw, "%d\n",N);
    fclose(fr);
    fclose(fw);
    return 0;
}

Entrambe le versioni vanno fuori tempo limite negli stessi 7 testcase

Grazie a entrambi per l’interessamento.


#5

Mi infilo nella conversazione dopo un paio di mesi; ma map é generalmente implementata come bst (le chiavi infatti sono sortate). Quindi l’inserimento non é in O(1)