結果

問題 No.3047 Verification of Sorting Network
ユーザー tails
提出日時 2025-03-07 03:08:47
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 218 ms / 2,000 ms
コード長 1,661 bytes
コンパイル時間 1,513 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-07 03:09:00
合計ジャッジ時間 12,764 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
int a[351],b[351];
char c[351];
char d[351];
int dn;
char e[27];
int en;

void f(int i){
	if(i==m){
		rep(k,n-1){
			if(!e[k]&&c[k]!=0&&c[k+1]!=1){
				e[k]=1;
				++en;
			}
		}
	}else{
		int cai=c[a[i]];
		int cbi=c[b[i]];
		if(cai==0||cbi==1){
			f(i+1);
		}else{
			if(!d[i]){
				d[i]=1;
				--dn;
			}
			if(cai==1||cbi==0){
				c[a[i]]=cbi;
				c[b[i]]=cai;
			}else{
				c[a[i]]=0;
				f(i+1);
				c[a[i]]=1;
				c[b[i]]=1;
			}
			f(i+1);
			c[a[i]]=cai;
			c[b[i]]=cbi;
		}
	}
}

int main(){
	rd_init();
	char*wp=wbuf;
	int t=rd();
	repeat(t){
		n=rd();
		m=rd();
		rep(i,m) a[i]=rd()-1;
		rep(i,m) b[i]=rd()-1;
		rep(i,m) c[i]=-1;
		rep(i,m) d[i]=0;
		dn=m;
		rep(i,n-1) e[i]=0;
		en=0;
		f(0);
		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