1

みなさん、こんにちは。私は非常に多くの情報を提供しなければならないコーディングコンテストの問題を解決しています。

問題で述べたように-入力ファイルのサイズはほぼ8MBに達する可能性があるため、高速I/O方式を使用していることを確認してください。

入力はテストケースの数として与えられます。次に、正方行列の次元n。次に、マトリックス全体を次のように

2

3

2 6 4

4 8 9

7 9 4

2

8 4

15 4

ネット上のどこかからコードを入手しましたが、これでもTime Limit Exceededというメッセージが表示されるため、何の役にも立たないと思います。次のコードが高速入力を行うかどうかを教えてください

#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;
}

そして、この場合、intの入力を読み取る最速の方法を教えてください

事前にどうもありがとうございました

4

2 に答える 2

2

getchar unlocked は、SPOJ や Codechef などのオンライン ジャッジで問題の入力を取得する場合にも非常に高速です。コンソールから整数を読み取る関数を次に示します。

#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;
}

もう 1 つの非常に高速な方法は、バッファーを使用し、文字バッファーで入力を読み取ることです。以下の方法で説明

#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 */
}
于 2014-08-19T16:10:14.003 に答える
2

入力を読み取るためだけに TLE を取得していますか? データを読み取るだけのコードを送信して、データの読み取り操作にかかる時間を確認してください。次のgets基本コードは、約10MBのデータ ファイルを読み取るのに約0.50 秒かかりますが、バージョンは約1 秒かかります。scanf

gets メソッドを使用して入力を読み取ります。

#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 バージョン:

#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;
}
于 2013-01-08T06:42:47.247 に答える