結果

問題 No.918 LISGRID
ユーザー beet
提出日時 2019-10-25 23:14:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 3,190 bytes
コンパイル時間 2,643 ms
コンパイル使用メモリ 225,352 KB
最終ジャッジ日時 2025-01-08 01:45:32
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
struct TopologicalSort{
vector< set<int> > G;
vector<int> used,indeg,ps;
TopologicalSort(){}
TopologicalSort(int n):G(n),used(n,0),indeg(n,0){}
void add_edge(int s,int t){
G[s].emplace(t);
indeg[t]++;
}
void bfs(int s){
queue<int> que;
que.emplace(s);
used[s]=1;
while(!que.empty()){
int v=que.front();que.pop();
ps.emplace_back(v);
for(int u:G[v]){
indeg[u]--;
if(indeg[u]==0&&!used[u]){
used[u]=1;
que.emplace(u);
}
}
}
}
vector<int> build(){
int n=G.size();
for(int i=0;i<n;i++)
if(indeg[i]==0&&!used[i]) bfs(i);
return ps;
}
};
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
// AtCoder
const i64 CYCLES_PER_SEC = 2000000000;
struct Timer {
i64 start;
Timer(){reset();}
void reset(){start=getCycle();}
inline double get(){return (double)(getCycle()-start)/CYCLES_PER_SEC;}
inline i64 getCycle(){
u32 low,high;
__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
return ((i64)low)|((i64)high<<32);
}
};
Timer timer;
//INSERT ABOVE HERE
signed main(){
int h,w;
cin>>h>>w;
vector<int> as(h),bs(w);
for(int i=0;i<h;i++) cin>>as[i];
for(int i=0;i<w;i++) cin>>bs[i];
auto check=
[&](){
TopologicalSort G(h*w);
auto idx=[&](int y,int x){return y*w+x;};
for(int i=0;i<h;i++){
vector<int> vs(w);
for(int j=0;j<w;j++) vs[j]=w-(j+1);
for(int j=w-as[i],k=0;j<w;j++) vs[j]=k++;
using P = pair<int, int>;
vector<P> vp;
for(int j=0;j<w;j++)
vp.emplace_back(vs[j],j);
sort(vp.begin(),vp.end());
for(int j=0;j+1<w;j++)
G.add_edge(idx(i,vp[j].second),idx(i,vp[j+1].second));
}
for(int j=0;j<w;j++){
vector<int> vs(h);
for(int i=0;i<h;i++) vs[i]=h-(i+1);
for(int i=h-bs[j],k=0;i<h;i++) vs[i]=k++;
using P = pair<int, int>;
vector<P> vp;
for(int i=0;i<h;i++)
vp.emplace_back(vs[i],i);
sort(vp.begin(),vp.end());
for(int i=0;i+1<h;i++)
G.add_edge(idx(vp[i].second,j),idx(vp[i+1].second,j));
}
auto ps=G.build();
if((int)ps.size()!=h*w) return;
vector< vector<int> > ans(h,vector<int>(w,0));
for(int i=0;i<h*w;i++)
ans[ps[i]/w][ps[i]%w]=i+1;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(j) cout<<" ";
cout<<ans[i][j];
}
cout<<endl;
}
exit(0);
};
for(int i=0;i<4;i++){
if(i&1) sort(as.begin(),as.end());
else sort(as.rbegin(),as.rend());
if(i&2) sort(bs.begin(),bs.end());
else sort(bs.rbegin(),bs.rend());
check();
}
random_device rd;
mt19937 mt(rd());
while(timer.get()<1.9){
shuffle(as.begin(),as.end(),mt);
shuffle(bs.begin(),bs.end(),mt);
check();
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0