結果
問題 | No.918 LISGRID |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;// AtCoderconst 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 HEREsigned 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;}