結果
問題 | No.2967 Nana's Plus Permutation Game |
ユーザー |
![]() |
提出日時 | 2024-11-16 16:25:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 568 ms / 2,000 ms |
コード長 | 1,131 bytes |
コンパイル時間 | 4,498 ms |
コンパイル使用メモリ | 256,580 KB |
最終ジャッジ日時 | 2025-02-25 04:34:35 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 65 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000000LL int query(int i,int j){ cout<<1<<' '<<i<<' '<<j<<endl; int res; cin>>res; return res; } int main(){ int N; cin>>N; scc_graph G(N); vector<vector<int>> E(N); rep(i,N){ int res = query(i+1,i+1); if(res!=-1){ G.add_edge(i,res-1); E[i].push_back(res-1); } } auto s = G.scc(); vector<int> pos(N); rep(i,N)pos[s[i][0]] = i; vector<int> dp(N,1); for(int i=N-1;i>=0;i--){ int ma = 0; int v = s[i][0]; rep(j,E[v].size()){ int u = E[v][j]; ma = max(ma,dp[pos[u]]); } dp[i] = ma+1; } int ii = 0; rep(i,N){ if(dp[i]>dp[ii])ii = i; } int v = s[ii][0]; rep(i,N){ if(v==i)continue; int res = query(v+1,i+1); if(res!=-1){ G.add_edge(v,res-1); G.add_edge(i,res-1); } G.add_edge(v,i); } s = G.scc(); vector<int> ans(N); rep(i,N)ans[s[i][0]] = i; cout<<2; rep(i,N){ cout<<' '<<ans[i]+1; } cout<<endl; return 0; }