結果

問題 No.918 LISGRID
ユーザー LayCurseLayCurse
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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(&deg, 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));
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0