Codeforces #148 div1A,div2C Not Wool Sequences
これからボチボチCodeforcesの和訳＆解説＆コードとかを公開していくかもしれません
基本的に、自分が受けたコンテストを1日後ぐらいに公開する予定です
URL: http://www.codeforces.com/contest/238/problem/A
問題概要
ある数列について、隣接した空でない部分列のxorを取ったものが0となる部分列があるとき、その数列はWool sequenceとする
長さNで要素が0から(2^m)-1でWool Sequenceでない数列の数を10^9+9で割ったあまりを求めよ。
1<=N,m<=10^5
方針
i番目まで決まったとすると、
[0,i)までの数列の部分列にxorして0となるものはない。
i番目をx(x!=0)という数にして、[j,i](0<=j
using namespace std; static const int INF =500000000; typedef pair<int,int> pi; const long long mod=1000000009; long long mpow(long long a,int k){ long long res=1; while(k){ if(k&1){ res=res*a%mod; } a=a*a%mod; k>>=1; } return res; } int main(){ int n,m; cin>>n>>m; long long res=1; for(int i=0;i<n;++i){ res*=mpow(2,m)-1-i; res%=mod; } cout<<res<<endl; return 0; }
うさこテスター
USACOの最近2年ぐらいはジャッジに載ってないらしいので適当に使っているC++用のテスターをupします(需要あるのか・・・？)
USACO,解こう！（勧誘） http://www.usaco.org/index.php?page=contests
Main内は、グローバル変数も初期化が必要なので注意
ちょっと（入力、解答ファイル名）変更すれば他のにも転用可能です
解のうちどれか一つを出力、任意の順番で出力、といった形式には対応していないので注意
int Main(){ } const int TESTNUM=12;//THE NUMBER OF TEST CASES int main(){ Main();return 0;//DELETE THIS LINE WHEN TEST for(int i=1;i<=TESTNUM;++i){ stringstream ss;ss<<i; string input="I."+ss.str(),output="O2."+ss.str(),answer="O."+ss.str(); freopen(input.c_str(),"r",stdin); FILE* fp=freopen(output.c_str(),"w",stdout); Main(); fclose(fp); ifstream cin1(output.c_str()),cin2(answer.c_str()); string a,b; while(1){ if(cin1.eof() && cin2.eof()) break; cin1>>a; cin2>>b; if(a!=b){ fprintf(stderr,"FAIL in test %d\n",i); fflush(stderr); return 0; } } } fprintf(stderr,"Accepted\n"); return 0; }
IOI2012-適当に
なんか大会中にちょくちょく書く予定でしたがかけなかったのでまとめて書きます
Day0-移動
- 朝は成田のホテルで。オリセンよりおいしい
- 空港に入る。写真とか取る。飛行機乗る。特にトラブルなし
- 時間的に、飛行機内では起きているべきな気がしたのでずっと起きてアニメ（なのはA's）を見る。映画見たので内容大体知ってた。面白かった
- フランクフルト乗り継ぎ。厳しいという噂があったが全然そんなことなかった。
- 空港広い。商品がべらぼうに高い。
- A's見終わって、StrikerSの4話ぐらいまで見る。
- Arrows Tab,再起動すると30%充電が吹っ飛んだり、充電の残りが減らないまま3時間持ったりとよく分からない。(行きも帰りも9hrぐらいは持った)
- ミラノ着く。百万都市とは思えない空港のショボさ。
- バスに乗ってthe Garda Village（ガルビレ）へ。
- 隣の人と話す機会を伺っていたが2時間ぐらい掛けてようやく"Hello"を言えた。Slovakia人だった
- 適当に話す。 are you sure you'll get a gold medal?と聞いて、I hope I'll get itとか返された。
- ガルビレ着く 部屋の案内とかされる。
- 飯を食って、寝る
- 部屋の2段ベッドの2階部分に柵がなかったりいろいろひどいので、部屋の改造する
Day1-Opening Ceremony&practice
Day2-Contest Day1
- コンテストこわい＞＜
- 警察の車が道を少し封鎖していて、VIP的何かを感じた。
- ハエがまだいる。
- 安定の遅延スタート。
- なぜかこの日は問題文に目を通して計画を立てるということをせず、見た問題から解き始めてしまった。
- おどめたのsubtask1,2の後ringsバグって死ぬ。3hr&30minぐらい使ったが20点しか取れなかった。
- 残りの時間で適当に部分点を集める。120点100位以下（絶望）
- 悲しくなりますよ〜ホント
- 金メダル絶望的
Day3-Gardaland
- 雨が降っている。semiexp[雨を感じるかは選択制にすべき]
- 怖そうなアトラクションに乗る。しばらくして危険組＆安全組に分かれる（自分は危険組）
- Oh Oh Oh Gardaland~~（http://www.youtube.com/watch?v=bsRxQospbyk）
- やばそうなアトラクションにたくさん乗る。たのしい。
- 夜寝るとき、アトラクションの乗りすぎで体がふわふわ感じられた。
Day4-Contest Day2
- コンテストこわい＞＜
- ハエ、少しは少なくなったがまだいる。
- 安定の遅延スタート
- 今回は一昨日の反省を生かし、まず全部読む。
- tournament、やればできそう。ゴリゴリ。
- 2WAののち、2時間弱でAC。うれしい
- cityの55点はやるだけなので書く。1WAののち55点取れた
- supperで満点近く取れるとうれしいので頑張って考えるが分からん。
- 仕方ないので33点ぐらいの部分点狙う。意外と実相に手こずる。
- 頑張って32点ぐらい取る。ちょっとした改善を入れて40点にする。
- そのまま終わり。195点
- まあ、今日の結果には満足。day2では19位
- 合わせて38位で銀。day1くそぽよ杉って一番言われてるから（金は27位ぐらいまで）
Day5-Venezia
- 朝早く起きてバス->電車でveneziaに行く。
- Iranの人に名刺を配る。havalizaさんが自分しっててうれしかった。
- 電車では寝る。
- veneziaについた。中型船のようなものに乗る。
- 風景綺麗だった。
- 船から降り、次に入る建物の前でかなり待たされる
- 適当に観光をする。いろいろ回った後、昼食を食べ、芸術品が並んだ所に行く。
- りんごさんが芸術品でいろいろな遊びをしていた。
- AustralianとかKoreanとかGreekと交流とかする
- よく分からない人の演説見たいなのを聞く。
- 帰る。italian queueがやばいし虫が多くてなかなか不快
- 名刺切れたなーと思って名刺ケース見たらなのは映画券が出てきて爆笑
- 帰りの船で、HAYATE YAGAMIという文字と人間系のイラストが書かれた台湾の人と話したりする。愉快な人だった。(映画券自慢した)
- りんごさんによると、twitterでは髪型や髪の毛の色を変えただけのアイコンが大量に存在していて訳が分からないらしい
Day6-Sirmione&Closing Ceremony
- ゆっくりSirmioneへ。
- みかんさん湖に落ちました。鳥に触ったらしい
- レーティング3950のサイ
- ツアーを断るタイミングを失い、よく分からないツアーに付き合わされる。
- 城の解説を回避し、中心部への道を教えてもらう
- この日も雨が降ってた。
- アイスとか、ピザとか食べる。おいしい
- 昼食のためガルビレに戻る。
- setというゲームをhosさんやother contestantsとする。
- closing ceremony会場へ。メダルで席が分けられているらしい・w・
- 適当にceremonyをやり過ごし、メダルも難なくもらった。
- 突然拍手が何回も沸いた。"つまらん説明早く止めろ"と言わんとしている
- touristかっこいい！！Hoさんもかっこよかった
- Russia,USA,Singaporeとかと交流する。scott_wuさんが自分知っててうれしかった。
- farewell partyかとおもったらfarewell dinnerで、ただのcrowded dinnerだった。
- 交流あまりしないで帰る。寝る
Day7-移動
Day8-移動＆表敬訪問
- semiexp[飛行機に乗ってると物理的に腹が立つ]
- 成田空港を抜けて、成田expを使って東京へ。
- 内閣改造なので政務官か何かの人に会った。まあいい人だった。
- 帰る。ねむい
Day9-風邪をひいています
全体的に
- 停電起こる。壊れるなあ
- belarus/russiaは全員イケメン
- あせってはいけない（戒め）
- うさぎさんがガルビレを闊歩していた。
- 魔法少女になりたい＆女装したくない となると、全裸魔法少女か男装魔法少女しかない（レベル高すぎる・・・）
- タバコ厳重に規制されるべき
- 来年は金メダル取るゾ〜〜
直前合宿
適当に書きます
- 朝起きる。荷物の最後の詰め込みする
- 車で成田まで行く
- 着く。生徒・チューターではsemiexpさんしかまだいなかった
- だんだん人が集まる。おすしさんがルールの翻訳を解説するPhase.有難いけどねむい
- その後はチューターsがIOI系問題の解説
- 壮行会。ちょっとだけ緊張した。父兄で来てるの自分の父だけで草
- 飯。おいしかったけど天ぷらがえび2本だった、悲しみ（えび好きじゃない） しかししょうがないのでほぼ生まれて初めてえびの天ぷら食べた。意外と普通だったがやっぱり食感が・・・
- 解説続き
- 個室に戻る。りんごさんのWin7を使って無線を飛ばして集まってネットやってた
- 今22:43 そろそろ寝なきゃ
IOI 2012に行ってきます
今年のIOIは9月23日から29日にかけて開催されます。
日本からは4人の代表が派遣されます。選手はsemiexpさん、hziwaraさん、tozangezanさんと僕です。
海外から出る強い人は、touristさん、yeputonsさん、sevenkplusさんなど。（RedCoder級でもごろごろいます）
IOIについての説明・出題内容はわかりやすいページがあるのでここを見てください(ちなみに、IOIは高校生の大会です) ->
http://qnighy.hatenablog.com/entry/20110719/1311078076
- 抱負
- 金メダルをとること
- 金メダル、約25人に配られますが、世界の代表が300人も来ているのでなかなか難しいです。ただへなちょこなミスを犯さなければ金メダルをとることは十分可能であると認識しています（まあへなちょこなミスを犯さないというのは相当難しいことですが・・・・）
- ちなみに、銀すら取れなかったら日本帰れないぐらいでいい気がする
- 積極的に国際交流する
- そもそも外国に行って外国人と話した経験ほとんどないのでかなり不安です。 まあでも自分から声かけていけばシカトされることはないと思うのでどうにかなるかなー、とも あと、強い人を生で見てみたいです
- どちらかというと名刺配りまくる感じより名前覚えてもらうぐらいの人を何人か作りたいです
- 金メダルをとること
競技がある日は25日、27日です。今年もcontest scoreboardが外部の人には公開されるようなので、是非観戦してください！！（日本時間夕方5時からで割と日本人にもうれしい時間）
scoreboardや速報・ライブ映像とかのURLとかも分かり次第貼っていきます
http://www.ioi2012.org/direct-video/ ここでライブ映像とかありそう？暇だったら流して見てるとｵﾓﾛｲかも。来年IOI行く予定の人にとってもいいかもしれません。
ニュースレター速報も今年はJOI公式ページに作られる予定ですが、まだページ作ってないみたいです
scoreboardもどこにあるのかまだよく分からないですが、http://www.ioi2012.org/competition/results/ ここ辺りに何かしらのannounceはされると思います
IOI 2011 Elephants
http://www.ioi-jp.org/ioi/2011/tasks/day2/elephants_jpn.pdf
書いた。むずかった
平方分割、と言われても自明に思いつく程簡単でもない＆実装もそこそこ
（まあでも平方分割の実装としては標準的な気がする）
象を最初の方からB個ずつ分ける。
それぞれの象iについて、
- 象iより後ろの同じバケット内の象を被うために必要なカメラ
- その時に、最後のカメラはどこまで被えるか
を記憶。
あとは更新を頑張る。バケットが偏ってきたら全部破壊してやり直す
更新もしゃくとり使うとfasterでgood
Bをうまいこと決めると、O(N^1.5logN)ぐらいになります
subtask5は10秒ぐらいかかるので多分TLEです
API使わないで、入力データから直接読み込み＆プログラム内でチェックしてます
using namespace std; static const int INF =1000000005; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} typedef long long int lint; typedef pair<int,int> pi; int n,l,m; int pos[200000]; pi seq[200000]; int belong[200000],rank[200005],size[200005]; int need[200000],reach[200000]; static const int B=300; int each[200000/B+2][B*2+5]; int bn; void build(int k){ int j=size[k]-1; for(int i=size[k]-1;i>=0;--i){ int id=each[k][i],jd=each[k][j]; while(j>i && pos[jd]>pos[id]+l){ --j; jd=each[k][j]; } if(j+1<size[k]){ jd=each[k][j+1]; need[id]=need[jd]+1; reach[id]=reach[jd]; }else{ need[id]=1; reach[id]=pos[id]+l; } } } void build(){ for(int i=0;i<n;++i) seq[i]=make_pair(pos[i],i); sort(seq,seq+n); for(int i=0;i<n;++i){ belong[seq[i].second]=i/B; rank[seq[i].second]=i%B; each[i/B][i%B]=seq[i].second; } bn=(n-1)/B+1; pos[n]=INF; for(int i=0;i<bn;++i) size[i]=0; for(int i=0;i<n;++i) size[belong[i]]++; for(int i=0;i<bn;++i) build(i); } int main(){ scanf("%d%d%d",&n,&l,&m); for(int i=0;i<n;++i){ scanf("%d",&pos[i]); } int sub=0; while(n%B){ pos[n++]=-INF-10; sub=1; } build(); for(int hoge=0;hoge<m;++hoge){ int i,a,ans;scanf("%d%d%d",&i,&a,&ans); int buck=0; for(int j=0;j<bn;++j) if(pos[each[j][0]]<=a){ buck=j; } --size[belong[i]]; ++size[buck]; int flag=0; for(int j=0;j<bn;++j) if(size[j]==0 || size[j]>B*2){ pos[i]=a; build(); flag=1; break; } if(!flag){ ++size[belong[i]]; --size[buck]; for(int j=rank[i];j<size[belong[i]]-1;++j){ int nxt=each[belong[i]][j+1]; each[belong[i]][j]=nxt; rank[nxt]--; } --size[belong[i]]; build(belong[i]); pos[i]=a; belong[i]=buck; for(int j=0;j<size[buck]+1;++j) if(j==size[buck] || pos[each[buck][j]]>=a){ for(int k=size[buck]-1;k>=j;--k){ each[buck][k+1]=each[buck][k]; rank[each[buck][k]]++; } ++size[buck]; each[buck][j]=i; rank[i]=j; break; } build(buck); } int res=0,cur=0; for(int j=0;j<bn;++j){ res+=need[each[j][cur]]; int r=reach[each[j][cur]]; while(j<bn-1){ int lb=-1,ub=size[j+1]; while(ub-lb>1){ int md=(ub+lb)>>1; if(pos[each[j+1][md]]<=r) lb=md; else ub=md; } if(lb+1==size[j+1]){ ++j; continue; } cur=lb+1; break; } } res-=sub; if(res!=ans){ printf("%d %d\n",res,ans); puts("ERROR"); } } return 0; }
夏のいろいろ（コード）
Supercon 提出コード
/******************************************************************* SuperCon12: Template for input output procedures file: sc12_template2E.cu by S.Kishimoto and O.Watanabe Aug. 17, 2012 ver.2 by T.Endo and A.Nukada Aug. 22, 2012 Remark: @@@ for test/tentative statements *********************************************************************/ /********* Template Part (1) NO CHAGNGE FROM HERE **********/ #include<stdio.h> #include<stdlib.h> #include<time.h> #include<sys/time.h> // @@@ two include statements for CUDA #include<cuda.h> #include<cuda_runtime.h> // @@@ Examination (Honban) parameters FROM HERE #define MAXlid 5 #define MAXst 40 #define MAXntr 180 #define MAXtd 7 #define MAXtid 6000 #define MAXtm4test 1200 // @@@ Examination (Honban) parameters UP TO HERE // @@@ Test parameters FROM HERE //#define MAXlid 3 //#define MAXst 20 //#define MAXntr 90 //#define MAXtd 4 //#define MAXtid 4000 //#define MAXtm4test 120 // @@@ Test parameters UP TO HERE #define MAXtm 1200 #define MAXtvtm 7 #define MAXstPline 20 //------------ int Nst; int Ntid; int maxDist; short int trainTBnst[MAXtid]; short int trainTB[MAXtid][MAXstPline][3]; int outroute[MAXtm][3][2]; //------------ void input() { int i,j,k; scanf("%d", &Nst); int nlid; scanf("%d", &nlid); int yobi; for(i=0; i<nlid; i++) { int m; scanf("%d", &m); for(j=0; j<m; j++) scanf("%d", &yobi); } for(i=0; i<Nst; i++) for(j=0; j<Nst; j++) scanf("%d", &yobi); scanf("%d", &Ntid); int tid; for(tid=0; tid<Ntid; tid++) { int m; scanf("%d", &m); trainTBnst[tid] = m; int j; for(j=0; j<m; j++) { int st , tm, dist; scanf("%d %d %d", &st, &tm, &dist); trainTB[tid][j][0] = st; trainTB[tid][j][1] = tm; trainTB[tid][j][2] = dist; } } for(i=0; i<MAXtm; i++) for(j=0; j<3; j++) for(k=0; k<2; k++) outroute[i][j][k] = -1; // pay "CUDA tax" now { void *p; cudaError_t err; err = cudaMalloc(&p, 4096); if (err != cudaSuccess) { fprintf(stderr, "cudaMalloc in input() failed!\n"); exit(1); } err = cudaFree(p); if (err != cudaSuccess) { fprintf(stderr, "cudaFree in input() failed!\n"); exit(1); } } } void output() { int i,j; printf("##########\n"); printf("maxDist: %d\n",maxDist); for(i=0; i<MAXtm; i++) { for(j=0; j<3; j++) printf("%2d %2d ", outroute[i][j][0], outroute[i][j][1]); printf("\n"); } } /********* Template Part (1) NO CHANGE UP TO HERE **********/ /********* Your Program Part (1) FROM HERE **********/ int M,V; struct edge{ int from,to; short int cost,cap; int rev; bool type; short int id; }; struct edge2{ int from,to; short int cost,cap; int rev; }; const int INF=30000; int source,sink; const int BASE=100; const int MAX_V=100000/*MAXst*MAXtm*2+5*/,MAX_E=MAXstPline*MAXtid*2+MAXst*MAXtm*4+MAXst*2+BASE; struct edge es[MAX_E]; struct edge2 es2[MAX_E]; struct edge *g[MAX_V][22]; int deg[MAX_V]; void prep(){ int i,j; M=0; V=Nst*MAXtm*2+5; source=V-3; sink=V-2; for(i=0;i<Ntid;++i){ int back=-1,backtime; for(j=0;j<trainTBnst[i];++j){ int sid=trainTB[i][j][0],tm=trainTB[i][j][1],dist=trainTB[i][j][2]; if(back!=-1){ es[M]=(edge){(backtime*Nst+back)*2+1,(sid+tm*Nst)*2,dist,1,M+1,1,i};++M; es[M]=(edge){(sid+tm*Nst)*2,(backtime*Nst+back)*2+1,-dist,0,M-1,0,i};++M; } backtime=tm;back=sid; } } for(i=0;i<Nst*MAXtm;++i){ es[M]=(edge){i*2,i*2+1,0,1,M+1,1,-1};++M; es[M]=(edge){i*2+1,i*2,0,0,M-1,0,-1};++M; } for(i=0;i<Nst;++i){ es[M]=(edge){source,i*2,0,1,M+1,1,-1};++M; es[M]=(edge){i*2,source,0,0,M+1,0,-1};++M; es[M]=(edge){(i+(MAXtm-1)*Nst)*2+1,sink,0,1,M+1,1,-1};++M; es[M]=(edge){sink,(i+(MAXtm-1)*Nst)*2+1,0,0,M-1,0,-1};++M; } for(i=0;i<Nst*(MAXtm-1);++i){ es[M]=(edge){i*2+1,(i+Nst)*2,0,1,M+1,1,-1};++M; es[M]=(edge){(i+Nst)*2,i*2+1,0,0,M-1,0,-1};++M; } for(i=0;i<M;++i) g[es[i].from][deg[es[i].from]++]=&es[i]; } short int cost[MAX_V]; int prevv[MAX_V],preve[MAX_V]; void max_cost_flow_1(int f=3){//for single-thread int i,j; int first_loop=1; while(f>0){ for(i=0;i<V;++i){ prevv[i]=preve[i]=cost[i]=-INF; } cost[source]=0; int changed=1; int loop=0; while(changed){ ++loop; changed=0; int first=0; for(i=source;i<V;(i==source?i=0:++i)){ if(i==source){ if(!first) first=1; else i=sink; } for(j=0;j<deg[i];++j){ struct edge* e=g[i][j]; if(e->cap && cost[e->to]<cost[e->from]+e->cost){ cost[e->to]=cost[e->from]+e->cost; prevv[e->to]=e->from; preve[e->to]=j; } } } if(first_loop==1){ first_loop=0; break; } } if(cost[sink]<0){ return; } int cur=sink; maxDist+=cost[sink]; while(cur!=source){ g[prevv[cur]][preve[cur]]->cap=0; es[g[prevv[cur]][preve[cur]]->rev].cap=1; cur=prevv[cur]; } --f; } } __device__ short int costDev[MAX_V]; __device__ unsigned int preveDev[MAX_V]; __global__ void initDev(){ costDev[blockIdx.x*blockDim.x+threadIdx.x]=SHRT_MIN; } __global__ void prep(int source){ costDev[source]=0; } __global__ void doMain(struct edge2* es,bool* changedFlag){ struct edge2* e=&es[blockIdx.x*blockDim.x+threadIdx.x]; if(e->cap && costDev[e->to]<costDev[e->from]+e->cost){ costDev[e->to]=costDev[e->from]+e->cost; preveDev[e->to]=blockIdx.x*blockDim.x+threadIdx.x; changedFlag[0]=true; } } __global__ void doMain2(struct edge2* es){ struct edge2* e=&es[blockIdx.x*blockDim.x+threadIdx.x]; if(e->cap && costDev[e->to]<costDev[e->from]+e->cost){ costDev[e->to]=costDev[e->from]+e->cost; preveDev[e->to]=blockIdx.x*blockDim.x+threadIdx.x; } } __global__ void set(bool* changedFlag){ changedFlag[0]=false; } __global__ void makepath2(int sink,int* maxDist,int source,struct edge2* es){ maxDist[0]+=costDev[sink]; int cur=sink; while(cur!=source){ es[preveDev[cur]].cap=0; es[es[preveDev[cur]].rev].cap=1; cur=es[preveDev[cur]].from; } } void max_cost_flow_2(int f=3){ while(M%BASE){ es[M++]=(edge){0,0,0,0,0,0,-1}; } int i; for(i=0;i<M;++i){ es2[i].from=es[i].from; es2[i].to= es[i].to; es2[i].cost=es[i].cost; es2[i].rev= es[i].rev; es2[i].cap= es[i].cap; } struct edge2* pos; bool* bpos; bool btmp[1];btmp[0]=false; cudaMalloc((void **)&bpos,sizeof(bool)); cudaMalloc((void **)&pos,sizeof(struct edge2)*M); cudaMemcpy(pos,es2,sizeof(struct edge2)*M,cudaMemcpyHostToDevice); int* maxDistDev; cudaMalloc((void **)&maxDistDev,sizeof(int)); int tmp[1]={maxDist}; cudaMemcpy(maxDistDev,tmp,sizeof(int),cudaMemcpyHostToDevice); int lastloop=0; while(f>0){ initDev<<<1000,100>>>(); prep<<<1,1>>>(source); cudaDeviceSynchronize(); int changed=V+1; int loop=0; while(changed--){ ++loop; if(loop>=lastloop/2 && loop%30==15){ set<<<1,1>>>(bpos); doMain<<<M/BASE,BASE>>>(pos,bpos); cudaMemcpy(btmp,bpos,sizeof(bool),cudaMemcpyDeviceToHost); if(btmp[0]==false) break; }else{ doMain2<<<M/BASE,BASE>>>(pos); } } lastloop=loop; makepath2<<<1,1>>>(sink,maxDistDev,source,pos); --f; } cudaMemcpy(tmp,maxDistDev,sizeof(int),cudaMemcpyDeviceToHost); maxDist=tmp[0]; cudaMemcpy(es2,pos,sizeof(struct edge2)*M,cudaMemcpyDeviceToHost); cudaFree(maxDistDev); cudaFree(pos); cudaFree(bpos); for(i=0;i<M;++i){ es[i].cap=es2[i].cap; } } void makepath(){ int i,j,k; for(i=0;i<3;++i){ int cur=source;//must front for(j=0;j<deg[cur];++j) if(g[cur][j]->cap==0){ g[cur][j]->type=0;g[cur][j]->cap=1; int to=g[cur][j]->to; cur=to; } while(cur!=sink){ int time=cur/2/Nst,st=cur/2%Nst; for(j=0;j<deg[cur];++j) if(g[cur][j]->cap==0 && g[cur][j]->type==1){ g[cur][j]->type=0;g[cur][j]->cap=1; cur=g[cur][j]->to; break; } for(j=0;j<deg[cur];++j) if(g[cur][j]->cap==0 && g[cur][j]->type==1){ g[cur][j]->cap=1;g[cur][j]->type=0; int to=g[cur][j]->to; if(to==sink){ outroute[time][i][0]=st; outroute[time][i][1]=-1; cur=sink; break; } if(to/2%Nst==st && time+1==to/2/Nst){ outroute[time][i][0]=st; outroute[time][i][1]=-1; cur=to; break; } int nxtTime=to/2/Nst; outroute[time][i][0]=st; outroute[time][i][1]=g[cur][j]->id; for(k=time+1;k<nxtTime;++k){ outroute[k][i][0]=-1; outroute[k][i][1]=g[cur][j]->id; } cur=to; break; } } } } /********* Your Program Part (1) UP TO HERE **********/ /********* Template Part (2) NO CHANGE FROM HERE **********/ int main() { struct timeval tstart, tlast; input(); gettimeofday(&tstart, NULL); /********* Template Part (2) NO CHANGE UP TO HERE **********/ /********* Your Program Part (2) FROM HERE **********/ prep(); max_cost_flow_1(1); max_cost_flow_2(2); makepath(); /********* Your Program Part (2) UP TO HERE **********/ /********* Template Part (3) NO CHANGE FROM HERE TO THE END **********/ gettimeofday(&tlast, NULL); printf("...end of execution... time %f\n", (double)(tlast.tv_sec - tstart.tv_sec)+ (double)(tlast.tv_usec - tstart.tv_usec)/ 1000000); output(); return 0; }
JOI夏セミ 最小カット乱択
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<vector> #define REP(i,m) for(int i=0;i<m;++i) #define REPN(i,m,in) for(int i=in;i<m;++i) #define ALL(t) (t).begin(),(t).end() #define fr first #define sc second #define mp make_pair #define pb push_back #define dump(x) cerr<<#x<<" = "<<x<<endl #define prl cerr<<"LINE:"<<__LINE__<<" is called"<<endl using namespace std; template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ' ;cerr<<endl;} const int INF=5e8; typedef pair<int,int> pi; static const int MAX_V=1005; int n; int mat[MAX_V][MAX_V],temp[MAX_V][MAX_V]; int memo[30][MAX_V][MAX_V]; int pos[MAX_V],sum[MAX_V]; int rec(int N,int dep){ if(N==2){ return mat[0][1]; } REP(i,N) REP(j,N) memo[dep][i][j]=mat[i][j]; int res=INF; REP(hoge,2){ REP(i,N) REP(j,N) mat[i][j]=memo[dep][i][j]; int h=N/sqrt(2.0),esnum=0; REP(i,N){ REP(j,N) esnum+=mat[i][j]; sum[i]=esnum; } REP(i,N) pos[i]=i; for(int i=N;i>h;--i){ if(esnum==0) return 0; int e=rand()%esnum; int s=INF,t=INF; REP(j,i) if(sum[pos[j]]>e){ s=j; break; } if(s>0) e-=sum[pos[s-1]]; int addit=0,sub; REP(j,i){ if(mat[pos[s]][pos[j]]>e){ sub=mat[pos[s]][pos[j]]; t=j;break; }else e-=mat[pos[s]][pos[j]]; } if(s>t) swap(s,t); REP(j,i) if(j!=s && j!=t){ mat[pos[j]][pos[s]]+=mat[pos[j]][pos[t]]; mat[pos[s]][pos[j]]+=mat[pos[t]][pos[j]]; addit+=mat[pos[t]][pos[j]]; } addit-=sub; sub*=2; REPN(j,i-1,t) pos[j]=pos[j+1]; REPN(j,t,s) sum[pos[j]]+=addit; REPN(j,i-1,t) sum[pos[j]]-=sub; esnum-=sub; } REP(i,N) REP(j,N) temp[i][j]=mat[i][j]; REP(i,h) REP(j,h) mat[i][j]=temp[pos[i]][pos[j]]; res=min(res,rec(h,dep+1)); } return res; } #include<ctime> int firstState[MAX_V][MAX_V]; int main(){ clock_t start=clock(),end; scanf("%d",&n); REP(i,n) REP(j,n) scanf("%d",&mat[i][j]); int res=INF,logN=0; while((1<<logN)<n) ++logN; REP(i,n) REP(j,n) firstState[i][j]=mat[i][j]; REP(hoge,logN){ REP(i,n) REP(j,n) mat[i][j]=firstState[i][j]; int temp=rec(n,0); printf("%d\n",temp); res=min(res,temp); } printf("%d\n",res); end=clock(); printf("time is %.5f\n",(end-start)/(double)CLOCKS_PER_SEC); return 0; }
