結果
問題 | No.1370 置換門松列 |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-29 22:33:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 851 bytes |
コンパイル時間 | 2,008 ms |
コンパイル使用メモリ | 200,272 KB |
最終ジャッジ日時 | 2025-01-18 09:32:00 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 25 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:16:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 16 | scanf("%d%d",&N,&M); | ~~~~~^~~~~~~~~~~~~~ main.cpp:17:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | rep(i,N){ scanf("%d",&A[i]); A[i]--; } | ~~~~~^~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> using namespace std; using LL=long long; using ULL=unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) int N,M; int A[100001]; vector<int> E[100000]; int I[100000]; vector<int> V; int ans[100000]; int main(){ scanf("%d%d",&N,&M); rep(i,N){ scanf("%d",&A[i]); A[i]--; } rep(i,N-2) if(A[i]==A[i+2]){ printf("No\n"); return 0; } rep(i,M) I[i]=0; rep(i,N-1){ if(i%2){ E[A[i+1]].push_back(A[i]); I[A[i]]++; } else{ E[A[i]].push_back(A[i+1]); I[A[i+1]]++; } } queue<int> Q; rep(i,M) if(I[i]==0) Q.push(i); while(Q.size()){ int p=Q.front(); Q.pop(); V.push_back(p); for(int e:E[p]) if(0==--I[e]) Q.push(e); } if(V.size()!=M){ printf("No\n"); return 0; } printf("Yes\n"); rep(i,M) ans[V[i]]=i+1; rep(i,M){ if(i) printf(" "); printf("%d",ans[i]); } printf("\n"); return 0; }