結果
問題 | No.918 LISGRID |
ユーザー |
![]() |
提出日時 | 2019-11-02 11:38:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 5,092 bytes |
コンパイル時間 | 2,971 ms |
コンパイル使用メモリ | 220,292 KB |
最終ジャッジ日時 | 2025-01-08 02:16:47 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;void *wmem;char memarr[96000000];template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );(*arr)=(T*)(*mem);(*mem)=((*arr)+x);}template<class T1> void sortA_L(int N, T1 a[], void *mem = wmem){sort(a, a+N);}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline void wt_L(char a){putchar_unlocked(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){putchar_unlocked('-');}while(s--){putchar_unlocked(f[s]+'0');}}template<class S> void arrInsert(const int k, int &sz, S a[], const S aval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}a[k] = aval;}template<class S, class T> void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}a[k] = aval;b[k] = bval;}template<class S, class T, class U> void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}for(i=sz-1;i>k;i--){c[i] = c[i-1];}a[k] = aval;b[k] = bval;c[k] = cval;}struct graph{int N;int *es;int **edge;void setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem){int i;N = N__;walloc1d(&es, N, mem);walloc1d(&edge, N, mem);walloc1d(&edge[0], M, mem);for(i=(0);i<(N);i++){es[i] = 0;}for(i=(0);i<(M);i++){es[A[i]]++;}for(i=(0);i<(N);i++){walloc1d(&edge[i], es[i], mem);}for(i=(0);i<(N);i++){es[i] = 0;}for(i=(0);i<(M);i++){edge[A[i]][es[A[i]]++] = B[i];}}int TopologicalSort(int res[], void *mem=wmem){int i;int j;int k;int rs;int *deg;int *q;int qs = 0;int qe = 0;walloc1d(°, N, &mem);walloc1d(&q, N, &mem);rs = 0;for(i=(0);i<(N);i++){deg[i] = 0;}for(i=(0);i<(N);i++){for(j=(0);j<(es[i]);j++){deg[edge[i][j]]++;}}for(i=(0);i<(N);i++){if(deg[i]==0){q[qe++] = i;}}while(qs < qe){i = q[qs++];res[rs++] = i;for(j=(0);j<(es[i]);j++){k = edge[i][j];deg[k]--;if(deg[k]==0){q[qe++] = k;}}}if(rs==N){return 1;}return 0;}};int H;int W;int A[400];int B[400];int res[400][400];graph g;int N;int M;int EA[400000];int EB[400000];int ind[200000];int main(){int i;wmem = memarr;rd(H);rd(W);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(H);Lj4PdHRW++){rd(A[Lj4PdHRW]);A[Lj4PdHRW] += (-1);}}{int KL2GvlyY;for(KL2GvlyY=(0);KL2GvlyY<(W);KL2GvlyY++){rd(B[KL2GvlyY]);B[KL2GvlyY] += (-1);}}sortA_L(H, A);sortA_L(W, B);N = H * W;for(i=(0);i<(H);i++){int j;for(j=(0);j<(A[i]);j++){arrInsert(M,M,EA,i*W+j,EB,i*W+j+1);}for(j=(A[i]);j<(W-1);j++){arrInsert(M,M,EA,i*W+j+1,EB,i*W+j);}}for(i=(0);i<(W);i++){int j;for(j=(0);j<(B[i]);j++){arrInsert(M,M,EA,j*W+i,EB,(j+1)*W+i);}for(j=(B[i]);j<(H-1);j++){arrInsert(M,M,EA,(j+1)*W+i,EB,j*W+i);}}g.setDirectEdge(N,M,EA,EB);g.TopologicalSort(ind);for(i=(0);i<(N);i++){res[ind[i]/W][ind[i]%W] = i+1;}for(i=(0);i<(H);i++){{int Q5VJL1cS;if(W==0){putchar_unlocked('\n');}else{for(Q5VJL1cS=(0);Q5VJL1cS<(W-1);Q5VJL1cS++){wt_L(res[i][Q5VJL1cS]);wt_L(' ');}wt_L(res[i][Q5VJL1cS]);wt_L('\n');}}}return 0;}// cLay varsion 20191102-1// --- original code ---// int H, W, A[400], B[400];// int res[400][400];//// graph g;// int N, M, EA[4d5], EB[4d5];// int ind[2d5];// {// rd(H,W,(A--)(H),(B--)(W));// sortA(H, A);// sortA(W, B);//// N = H * W;// rep(i,H){// rep(j,A[i]) arrInsert(M,M,EA,i*W+j,EB,i*W+j+1);// rep(j,A[i],W-1) arrInsert(M,M,EA,i*W+j+1,EB,i*W+j);// }// rep(i,W){// rep(j,B[i]) arrInsert(M,M,EA,j*W+i,EB,(j+1)*W+i);// rep(j,B[i],H-1) arrInsert(M,M,EA,(j+1)*W+i,EB,j*W+i);// }//// g.setDirectEdge(N,M,EA,EB);// g.TopologicalSort(ind);//// rep(i,N) res[ind[i]/W][ind[i]%W] = i+1;// rep(i,H) wt(res[i](W));// }