結果
問題 | No.1170 Never Want to Walk |
ユーザー |
|
提出日時 | 2020-08-14 21:53:46 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 1,626 bytes |
コンパイル時間 | 1,556 ms |
コンパイル使用メモリ | 130,904 KB |
実行使用メモリ | 21,648 KB |
最終ジャッジ日時 | 2024-10-10 15:04:36 |
合計ジャッジ時間 | 4,824 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <iostream>#include <iomanip>#include <algorithm>#include <array>#include <cassert>#include <utility>#include <vector>int main(void){std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(16);int n, A, B; std::cin >> n >> A >> B;std::vector<int> X(n); for(auto& itr : X) std::cin >> itr;std::vector<std::vector<int>> edge(n);std::vector<int> Y(n, 0);for(int i = 0; i < n; ++i){const int a = std::lower_bound(X.cbegin() + i, X.cend(), X[i] + A) - X.cbegin();const int b = std::upper_bound(X.cbegin() + a, X.cend(), X[i] + B) - X.cbegin();if(a == b) continue;edge[i].push_back(a); edge[a].push_back(i);if(a < b - 1){edge[i].push_back(b - 1); edge[b - 1].push_back(i);}++Y[a]; --Y[b - 1];}for(int i = 0; i + 1 < n; ++i) Y[i + 1] += Y[i];for(int i = 0; i + 1 < n; ++i) if(Y[i] > 0){ edge[i].push_back(i + 1); edge[i + 1].push_back(i); }std::vector<int> res(n, -1); std::vector<int> Connect(n, 0);std::vector<int> Stk(n);for(int i = 0, idx = 0; i < n; ++i) if(res[i] == -1){int pos = 0;res[i] = idx; ++Connect[idx]; Stk[pos++] = i; ++Connect[idx];while(pos--){const int v = Stk[pos];for(const int nv : edge[v]) if(res[nv] == -1){res[nv] = idx; ++Connect[idx];Stk[pos++] = nv;}}++idx;}for(int i = 0; i < n; ++i){std::cout << Connect[res[i]] - 1 << '\n';}return 0;}