結果
問題 | No.918 LISGRID |
ユーザー | beet |
提出日時 | 2019-10-25 23:14:45 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 3,190 bytes |
コンパイル時間 | 2,997 ms |
コンパイル使用メモリ | 234,168 KB |
実行使用メモリ | 29,092 KB |
最終ジャッジ日時 | 2024-09-13 08:32:58 |
合計ジャッジ時間 | 6,740 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 54 ms
18,576 KB |
testcase_02 | AC | 17 ms
8,448 KB |
testcase_03 | AC | 22 ms
10,624 KB |
testcase_04 | AC | 18 ms
8,832 KB |
testcase_05 | AC | 63 ms
21,968 KB |
testcase_06 | AC | 58 ms
20,532 KB |
testcase_07 | AC | 83 ms
27,852 KB |
testcase_08 | AC | 45 ms
17,844 KB |
testcase_09 | AC | 63 ms
22,724 KB |
testcase_10 | AC | 65 ms
22,496 KB |
testcase_11 | AC | 64 ms
22,372 KB |
testcase_12 | AC | 68 ms
24,112 KB |
testcase_13 | AC | 53 ms
20,176 KB |
testcase_14 | AC | 80 ms
26,344 KB |
testcase_15 | AC | 90 ms
29,092 KB |
testcase_16 | AC | 30 ms
13,016 KB |
testcase_17 | AC | 34 ms
13,952 KB |
testcase_18 | AC | 32 ms
13,056 KB |
testcase_19 | AC | 9 ms
6,400 KB |
testcase_20 | AC | 46 ms
16,740 KB |
testcase_21 | AC | 12 ms
7,296 KB |
testcase_22 | AC | 8 ms
6,016 KB |
testcase_23 | AC | 26 ms
11,520 KB |
testcase_24 | AC | 3 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 3 ms
5,376 KB |
testcase_35 | AC | 5 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 43 ms
16,336 KB |
testcase_38 | AC | 26 ms
12,160 KB |
ソースコード
#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; }