結果

問題 No.1282 Display Elements
ユーザー tsuishitsuishi
提出日時 2021-01-07 09:55:27
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 5,002 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-07 23:35:41
合計ジャッジ時間 5,136 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,496 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 0 ms
5,248 KB
testcase_10 AC 11 ms
5,248 KB
testcase_11 AC 11 ms
5,248 KB
testcase_12 AC 1 ms
5,248 KB
testcase_13 AC 4 ms
5,248 KB
testcase_14 AC 8 ms
5,248 KB
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// ***********************
// for debug
#define DEBUG2


#define NOP do{}while(0)
#ifdef DEBUG
#define TRACE(...) do{printf(__VA_ARGS__);fflush(stdout);}while(0)
#define TRACECR do{printf("\n");fflush(stdout);}while(0)
#else
#define TRACE(...) NOP
#define TRACECR NOP
#endif

#define PRINCR printf("\n")
#define NOCR(strig) do{char *p;p=strchr(strig,'\n');if(p)*p='\0';}while(0)
// The out-of-date function
#define	asctime(...)	asctime_s(...)
#define	atof(a)		strtod(a,'\0')
#define	atoi(a)		((int)strtol(a,'\0'))
#define	atol(a)		strtol(a,'\0')
#define	ctime(...)		ctime_s(...)
//#define	fopen(...)		fopen_s(...)
//#define	freopen(...)	freopen_s(...)
//#define	rewind(a)		fseek(a,0L,SEEK_SET)
//#define	setbuf(a,b)		setvbuf(a,b,_IOFBF,BUFSIZ)

// for stdio
#define INPUT(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)
static char *getinput( char* str );

// for readaility
typedef	long long	lolong;
const int	INF = 1e9;
const int	MOD = 1e9+7;
const lolong	LINF = 1e18;
static char *getinput(char* str) {char c;char *cp;cp=&str[0];c=fgetc(stdin);while( c != EOF ){if((c==' ')||( c=='\n')) break;*cp++=c;c=fgetc(stdin);}*cp='\0';return &str[0];}
#define	YES(a)	printf("%s",((a)?"YES":"NO"))
#define	Yes(a)	printf("%s",((a)?"Yes":"No"))
#define OK(a)	printf("%s",((a)?"OK":"NG"))
#define Ok(a)	printf("%s",((a)?"Ok":"Ng"))
#define	POSSIBLE(a)		printf("%s",((a)?"POSSIBLE":"IMPOSSIBLE"))
#define	Possible(a)		printf("%s",((a)?"Possible":"Impossible"))
#define SWAP(type,a,b) do{type _c;_c=a;a=b;b=_c;}while(0)
#define REP(a,b) for(int a=0;a<(int)(b);++a)
#define REP1(a,b) for(int a=1;a<=(b);++a)
#define FLOOP(a,b) for(a=0;a<(b);++a)
#define FLOOP1(a,b) for(a=1;a<=(b);++a)
#define	ABS(c)	 ((c)<0?(-(c)):(c))
#define LSB(i) ((i) & -(i))

#define INPBUF 50
#define BIGMAP 100002
#define	data_s	int
// ***********************
data_s	amap[BIGMAP];
data_s	bmap[BIGMAP];
// ***********************
static int cmpint_asc(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
static int cmpint_desc(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
// ***********************
// ***********************
// ***********************
// ***********************
int binarysearch(data_s arr[], int arr_len, int x) {
	int l = 0;
	int r = arr_len - 1;

    
	while (r - l > 1) {
		int mid;
		
		mid = l + (r - l) / 2;
        TRACE("l %d : mid %d : r %d [%d]\n", l, mid, r, x);
		if (x == arr[mid]  ) {
            TRACE("Hit %d[%d]\n", mid, x);
            if( mid > 0 ) {
    		    while( arr[mid -1] == x ) {
    		        mid--;
    		        if(mid<=0) { mid = 0; break; }
    		    }
            }
            TRACE("Ret m %d\n", mid);
			return mid;
		} else if (x > arr[mid] ) {
			l = mid;
		} else {
			r = mid;
		}
	}
	if (x == arr[r]) {
        TRACE("Hit %d[%d]\n", r, x);
	    while( arr[r] == x ) {
	        r--;
	        if(r<=0) { r = 0; break; }
	    }
        TRACE("Ret %d\n", r);
	    return r;
	}
	TRACE("Noting r%d\n", r);
	if( r <= arr_len -1 ) {
        while( arr[r] < x ) {
            r++;
            TRACE(".r%d.", r);
            if(r>=arr_len) { r = arr_len; break; }
        }
	}
    if( r > 0 ) {
        while( arr[r-1] >= x ) {
            r--;
            TRACE(".r%d.", r);
            if(r <= 0) { r = 0; break; }
        }
    }
    TRACE("ret r %d\n", r);
	return r;
}
// ***********************
int main(void) {
	char str[INPBUF];
	long	query,val;
	long	pl = 0;
	long	pts = 0;
	long	nowphase;

	// init
	// ready
	INPUT(str); sscanf( str , "%ld", &query );
	// start
	REP(i,query) {
		getinput( str );
		sscanf( str , "%ld", &val );
		amap[i] = (data_s)val;
	}
	//bmap[0] = 0;
	REP(i,query) {
		getinput( str );
		sscanf( str , "%ld", &val );
		bmap[i] = (data_s)val;
	}
	TRACE("A "); REP(k,query) TRACE("%d ", amap[k]); TRACECR;
	TRACE("B "); REP(k,query) TRACE("%d ", bmap[k]); TRACECR;

	qsort( amap, query, sizeof( amap[0] ) , (void*)cmpint_asc );
	TRACE("A "); REP(k,query) TRACE("%d ", amap[k]); TRACECR;

	for( nowphase = 0; nowphase < query ; nowphase++ ) {
		if( nowphase ) {
			qsort( bmap, nowphase+1, sizeof( bmap[0] ) , (void*)cmpint_asc );
		    TRACE("call( b , %ld , %d)\n", nowphase, amap[nowphase] );
		    TRACE("B "); REP(k,nowphase+1) TRACE("%d ", bmap[k]); TRACECR;
			pl = binarysearch( bmap , nowphase+1, amap[nowphase]  );	// 今回の得点
		} else {
		    TRACE("call( b , %ld , %d)\n", nowphase, amap[nowphase] );
			if( amap[0] > bmap[0] ) {
				pl = 1;
			} else {
				pl = 0;	// 今回の得点
			}
		    TRACE("B "); REP(k,nowphase+1) TRACE("%d ", bmap[k]); TRACECR;
		}

		TRACE("(%ld) x is %d. pl=%ld\n", nowphase, amap[nowphase], pl);
		pts += pl;
	}
	//qsort( bmap, query, sizeof( bmap[0] ) , (void*)cmpint_asc );
	//REP(k,query) TRACE("%lu ", bmap[k]); TRACECR;

	printf("%lu\n", pts );

	return 0;
}
0