結果

問題 No.2804 Fixer And Ratism
コンテスト
ユーザー tails
提出日時 2024-07-16 15:22:59
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,741 bytes
コンパイル時間 1,518 ms
コンパイル使用メモリ 25,344 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-08-10 07:06:15
合計ジャッジ時間 4,386 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:95:25: warning: implicit declaration of function ‘memcpy’ [-Wimplicit-function-declaration]
   95 |                         memcpy(wp,byr[r].name,byr[r].namelen);
      |                         ^~~~~~
main.c:1:1: note: include ‘<string.h>’ or provide a declaration of ‘memcpy’
  +++ |+#include <string.h>
    1 | #pragma GCC optimize("Ofast")
main.c:95:25: warning: incompatible implicit declaration of built-in function ‘memcpy’ [-Wbuiltin-declaration-mismatch]
   95 |                         memcpy(wp,byr[r].name,byr[r].namelen);
      |                         ^~~~~~
main.c:95:25: note: include ‘<string.h>’ or provide a declaration of ‘memcpy’
main.c:100:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
  100 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:101:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
  101 |         _exit(0);
      |         ^~~~~
main.c:101:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define times(e) for(typeof(e)_=e;_--;)

typedef unsigned long ulong;

char wbuf[1<<25];

struct{
	char const*name;
	int namelen;
	int fixed;
} byr[4001];
int rbyh[1<<16];
ulong b0h,b0b[64];
ulong b1h,b1b[64];
int z0,z1;

int main(){
	char*wp=wbuf;
	rd_init();
	int n=rd();
	int q=rd();
	times(q){
		int t=*rp;
		rp+=2;
		if(t=='1'){
			char const*name=rp;
			int h=0;
			for(int c;c=*rp++,c>=64;){
				h=h*29+c;
			}
			h&=0xffff;
			int namelen=rp-name-1;
			int r=rd();
			rbyh[h]=r;
			byr[r].name=name;
			byr[r].namelen=namelen;
			b0b[r>>6]|=1ul<<(r&63);
			b0h|=1ul<<(r>>6&63);
			z0+=1;
		}
		if(t=='2'){
			int x=rd();
			n-=x;
		}
		if(t=='3'){
			int h=0;
			for(int c;c=*rp++,c>=64;){
				h=h*29+c;
			}
			h&=0xffff;
			int r=rbyh[h];
			if(!byr[r].fixed){
				byr[r].fixed=1;
				if(!(b0b[r>>6]&=~(1ul<<(r&63)))){
					b0h&=~(1ul<<(r>>6&63));
				}
				z0-=1;
				b1b[r>>6]|=1ul<<(r&63);
				b1h|=1ul<<(r>>6&63);
				z1+=1;
			}
			int x=rd();
			n+=x;
		}
		while(z0+z1>n){
			int r;
			int r0=9999;
			if(z0){
				r0=__builtin_ctzl(b0h);
				r0=r0<<6|__builtin_ctzl(b0b[r0]);
			}
			int r1=9999;
			if(z1>n){
				r1=__builtin_ctzl(b1h);
				r1=r1<<6|__builtin_ctzl(b1b[r1]);
			}
			if(r0<r1){
				z0-=1;
				if(!(b0b[r0>>6]&=~(1ul<<(r0&63)))){
					b0h&=~(1ul<<(r0>>6&63));
				}
				r=r0;
			}else{
				z1-=1;
				if(!(b1b[r1>>6]&=~(1ul<<(r1&63)))){
					b1h&=~(1ul<<(r1>>6&63));
				}
				r=r1;
			}
			memcpy(wp,byr[r].name,byr[r].namelen);
			wp+=byr[r].namelen;
			*wp++='\n';
		}
	}
	write(1,wbuf,wp-wbuf);
	_exit(0);
}
0