結果
問題 | 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; // 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; }