結果
問題 | No.1778 括弧列クエリ / Bracketed Sequence Query |
ユーザー | tails |
提出日時 | 2021-12-07 16:39:37 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 1,227 bytes |
コンパイル時間 | 754 ms |
コンパイル使用メモリ | 30,732 KB |
実行使用メモリ | 9,996 KB |
最終ジャッジ日時 | 2023-09-22 01:34:47 |
合計ジャッジ時間 | 7,733 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
4,624 KB |
testcase_01 | AC | 10 ms
4,524 KB |
testcase_02 | AC | 9 ms
4,504 KB |
testcase_03 | AC | 7 ms
4,380 KB |
testcase_04 | AC | 10 ms
4,672 KB |
testcase_05 | AC | 20 ms
5,488 KB |
testcase_06 | AC | 11 ms
4,636 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 49 ms
9,740 KB |
testcase_09 | AC | 5 ms
4,376 KB |
testcase_10 | AC | 22 ms
5,864 KB |
testcase_11 | AC | 16 ms
5,280 KB |
testcase_12 | AC | 21 ms
5,660 KB |
testcase_13 | AC | 42 ms
9,560 KB |
testcase_14 | AC | 16 ms
5,608 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 45 ms
9,704 KB |
testcase_17 | AC | 52 ms
9,704 KB |
testcase_18 | AC | 50 ms
9,724 KB |
testcase_19 | AC | 45 ms
9,640 KB |
testcase_20 | AC | 58 ms
9,732 KB |
testcase_21 | AC | 1 ms
4,376 KB |
testcase_22 | AC | 1 ms
4,380 KB |
testcase_23 | AC | 9 ms
6,896 KB |
testcase_24 | AC | 9 ms
7,148 KB |
testcase_25 | AC | 18 ms
9,156 KB |
testcase_26 | AC | 19 ms
9,996 KB |
testcase_27 | AC | 10 ms
9,196 KB |
コンパイルメッセージ
main.c:20:1: 警告: 戻り値の型をデフォルトの ‘int’ にします [-Wimplicit-int] 20 | main(){ | ^~~~ main.c: 関数 ‘main’ 内: main.c:72:9: 警告: 関数 ‘write’ の暗黙的な宣言です [-Wimplicit-function-declaration] 72 | write(1,wbuf,wp-wbuf); | ^~~~~ main.c:73:9: 警告: implicit declaration of function ‘_exit’; did you mean ‘_Exit’? [-Wimplicit-function-declaration] 73 | _exit(0); | ^~~~~ | _Exit
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") char*mmap(); char wbuf[1<<25]; #define rd_skip() while(*rp++>=48) #define rd(v) long v=0;{long _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;} #define WTHI(v) {long _z=v,_n=0,_d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;} #define WTLO(v) {long _z=v,_n=8,_d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(long*)wp=_d;wp+=8;} #define wt(v) WTHI(v) #define rep(v,e) for(long v=0;v<e;++v) #define rep3(v,s,e) for(long v=s;v<e;++v) int ab[200002]; int nc[200002]; int pa[200002]; int st[100002]; main(){ char*rp=mmap(0l,1l<<25,1,2,0,0ll); char*wp=wbuf; rd(n); rd_skip(); long sn=0; st[sn++]=0; rep3(i,1,n+1){ if(!(*rp++&1)){ pa[i]=st[sn-1]; ++nc[st[sn-1]]; st[sn++]=i; }else{ long j=st[--sn]; ab[i]=j; ab[j]=i; } } ++rp; ab[0]=n+1; ab[n+1]=0; rep3(i,1,n+1){ if(nc[pa[i]]==1){ pa[i]=pa[pa[i]]; } } while(*rp){ rd(x); if(ab[x]<x) x=ab[x]; rd(y); if(ab[y]<y) y=ab[y]; if(ab[x]>ab[y]){ long t=x; x=y; y=t; } while(x<y){ y=pa[y]; } if(y==0){ *(int*)wp=*(int*)"-1\n"; wp+=3; }else{ wt(y); *wp++=' '; y=ab[y]; wt(y); *wp++='\n'; } } write(1,wbuf,wp-wbuf); _exit(0); }