結果

問題 No.3047 Verification of Sorting Network
ユーザー tails
提出日時 2025-03-07 10:52:43
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 85 ms / 2,000 ms
コード長 1,791 bytes
コンパイル時間 982 ms
コンパイル使用メモリ 31,872 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-07 10:52:49
合計ジャッジ時間 6,286 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:110:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
  110 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:111:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
  111 |         _exit(0);
      |         ^~~~~
main.c:111: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;
char e[27];
int en;

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];
				}
			}
		}
		rep(k,n-1){
			if(!e[k]&&!(c1&1<<k)&&!(c0&1<<k+1)){
				e[k]=1;
				++en;
			}
		}
	}
}

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;
		rep(i,n-1) e[i]=0;
		en=0;
		f();
		if(en){
			*wp++='N';
			*wp++='o';
			*wp++='\n';
			wt2(en);
			*wp++='\n';
			rep(i,n-1){
				if(e[i]){
					wt2(i+1);
					*wp++=' ';
				}
			}
			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