結果

問題 No.3047 Verification of Sorting Network
ユーザー tails
提出日時 2025-03-07 16:50:30
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 84 ms / 2,000 ms
コード長 1,851 bytes
コンパイル時間 783 ms
コンパイル使用メモリ 31,120 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-07 16:50:36
合計ジャッジ時間 5,884 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:106:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
  106 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:107:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
  107 |         _exit(0);
      |         ^~~~~
main.c:107: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 wt2(v) ({int _v=v;if(_v>=10)*wp++='0'+_v/10;*wp++='0'+_v%10;})
#define wt3(v) ({int _v=v;if(_v>=10){if(_v>=100)*wp++='0'+_v/100;*wp++='0'+_v/10%10;}*wp++='0'+_v%10;})
#define rep(v,e) for(typeof(e)v=0;v<e;++v)
#define repeat(e) for(typeof(e)_=e;_--;)

char wbuf[1<<25];
int n,m;
unsigned a[351];
unsigned b[351];
unsigned d[11];
unsigned e;

void f(){
	unsigned q[351*3];
	int qn=0;
	q[qn++]=0;
	q[qn++]=0;
	q[qn++]=0;
	while(qn){
		unsigned c0=q[--qn];
		unsigned c1=q[--qn];
		int i=q[--qn];
		for(;i<m;++i){
			if(c1&a[i]|c0&b[i]){
			}else{
				d[i>>5]|=1<<(i&31);
				if(c0&a[i]|c1&b[i]){
					if(c0&a[i]){
						c0^=a[i]|b[i];
					}
					if(c1&b[i]){
						c1^=a[i]|b[i];
					}
				}else{
					q[qn++]=i+1;
					q[qn++]=c1;
					q[qn++]=c0^a[i]|b[i];
					c1^=a[i];
				}
			}
		}
		e|=~(c1|c0>>1);
	}
}

int main(){
	rd_init();
	char*wp=wbuf;
	int t=rd();
	repeat(t){
		n=rd();
		m=rd();
		rep(i,m) a[i]=1<<rd()-1;
		rep(i,m) b[i]=1<<rd()-1;
		rep(i,11) d[i]=0;
		e=0;
		f();
		if(e&=(1<<n-1)-1){
			int en=__builtin_popcount(e);
			*wp++='N';
			*wp++='o';
			*wp++='\n';
			wt2(en);
			*wp++='\n';
			while(e){
				int i=__builtin_ctz(e);
				wt2(i+1);
				*wp++=' ';
				e&=e-1;
			}
			wp[-1]='\n';
		}else{
			*wp++='Y';
			*wp++='e';
			*wp++='s';
			*wp++='\n';
			int dn=m;
			rep(i,11){
				dn-=__builtin_popcount(d[i]);
			}
			wt3(dn);
			*wp++='\n';
			if(dn){
				rep(i,11){
					unsigned x=~d[i];
					while(x){
						int j=__builtin_ctz(x);
						if(i*32+j>=m){
							break;
						}
						wt3(i*32+j+1);
						*wp++=' ';
						x&=x-1;
					}
				}
				--wp;
			}
			*wp++='\n';
		}
	}
	write(1,wbuf,wp-wbuf);
	_exit(0);
}
0