Reputation: 5461
Hello everyone, I am solving a problem in a coding competition in which i have to give very large input.
As stated int the problem - The input file size could reach almost 8MB so be sure you are using fast I/O method.
The input is to be given as number of test cases. Then the dimension n of the square matrix. and then the whole matrix as
2
3
2 6 4
4 8 9
7 9 4
2
8 4
15 4
I have got a code from somewhere on net but i don't think that it is doing any help because with this also i am getting message Time Limit Exceeded. Please tell that if the following code will do fast input or not
#define BUF 406 // block size on my disk is 4KBs
char ibuf[BUF];
int ipt = BUF;
int read_uint() {
while (ipt < BUF && ibuf[ipt] < '0') ipt++;
if (ipt == BUF)
{
fread(ibuf, 1, BUF, stdin);
ipt = 0;
while (ipt < BUF && ibuf[ipt] < '0') ipt++;
}
int n = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
if (ipt == BUF)
{
fread(ibuf, 1, BUF, stdin);
ipt = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
}
return n;
}
And please tell the fastest method of reading input for int in this case
Thank You very much in advance
Upvotes: 1
Views: 6258
Reputation: 337
getchar unlocked also is very fast when it comes to taking input for problems on online judges like SPOJ or Codechef etc. Here is the function which reads an integer from Console
#define gc getchar_unlocked
void scan_integer( int &x )
{
register int c = gc();
x = 0;
int neg = 0;
for( ; ((c<48 || c>57) && c != '-'); c = gc() );
if( c=='-' ) {
neg=1;
c=gc();
}
for( ;c>47 && c<58; c = gc() ) {
x = (x << 1) + (x << 3) + c - 48;
}
if( neg )
x=-x;
}
Another very fast way is to use buffers and reading the input in a charecter buffer. Explained in following way
#define MAXIMUM_BUFFER_CAPACITY 15000000
char buffer_to[MAXIMUM_BUFFER_CAPACITY];
char *buffer_ptr = buffer_to;
int scan_integer()
{
int k = 0;
while( *buffer_ptr < 33 )
buffer_ptr++;
do {
k = k*10 + *buffer_ptr++ - '0';
} while(*buffer_ptr > 32);
return k;
}
int main()
{
fread(buffer_to, 1, MAXIMUM_BUFFER_CAPACITY, stdin);
int n;
n = scan_integer();
/* Use n */
}
Upvotes: 2
Reputation: 56
Are you getting TLE just for reading the inputs? Make sure how much time data-reading operation takes by submitting a code which only reads the data. The following gets
base code take about 0.50s to read about 10MB data file while scanf
version take about 1s
Read input using gets method:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
int matrix[100][100];
int main () {
char arr[1200], *p;
int n, j;
clock_t tStart = clock();
gets(arr);
n = atoi(arr);
for (; n--;) {
gets(arr);
int siz = atoi(arr);
for (int i=0; i<siz; i++) {
gets(arr);
p = strtok(arr, " ");
j=0;
while(p != NULL) {
matrix[i][j++] = atoi(p);
p = strtok(NULL, " ");
}
}
}
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
return 0;
}
scanf version:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
int matrix[100][100];
int main () {
int n, j;
clock_t tStart = clock();
scanf("%d", &n);
for (; n--;) {
int siz;
scanf("%d", &siz);
for (int i=0; i<siz; i++) {
j=0;
while(j<siz) {
scanf("%d", &matrix[i][j++]);
}
}
}
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
return 0;
}
Upvotes: 2