結果

問題 No.3047 Verification of Sorting Network
ユーザー tails
提出日時 2025-03-07 16:37:55
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 85 ms / 2,000 ms
コード長 1,754 bytes
コンパイル時間 701 ms
コンパイル使用メモリ 29,824 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-07 16:38:01
合計ジャッジ時間 5,977 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:104:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
  104 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:105:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
  105 |         _exit(0);
      |         ^~~~~
main.c:105: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];
char d[351];
int dn;
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{
				if(!d[i]){
					d[i]=1;
					--dn;
				}
				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,m) d[i]=0;
		dn=m;
		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';
			if(dn){
				wt3(dn);
				*wp++='\n';
				rep(i,m){
					if(!d[i]){
						wt3(i+1);
						*wp++=' ';
					}
				}
				wp[-1]='\n';
			}else{
				*wp++='0';
				*wp++='\n';
				*wp++='\n';
			}
		}
	}
	write(1,wbuf,wp-wbuf);
	_exit(0);
}
0