結果
問題 | No.2771 Personal Space |
ユーザー |
![]() |
提出日時 | 2024-05-31 22:29:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 339 ms / 2,000 ms |
コード長 | 5,639 bytes |
コンパイル時間 | 6,781 ms |
コンパイル使用メモリ | 328,292 KB |
実行使用メモリ | 29,572 KB |
最終ジャッジ日時 | 2024-12-21 00:09:50 |
合計ジャッジ時間 | 13,374 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using ll = long long;using ql = queue<ll>;using sl = set<ll>;using vl = vector<ll>;using msl = multiset<ll>;using Graph = vector<vector<ll>>;using P = pair<ll, ll>;template <typename T> inline bool chmax(T &a, T b) {return ((a < b) ? (a = b, true) : (false));}template <typename T> inline bool chmin(T &a, T b) {return ((a > b) ? (a = b, true) : (false));}#define YES \{ \cout << "Yes\n"; \exit(0); \}#define NO \{ \cout << "No\n"; \exit(0); \}#define rep1(i, n) for(ll i = 1; i <= ((ll)n); ++i)#define rep(i, n) for(ll i = 0; i < ((ll)n); ++i)#define ALL(a) (a).begin(), (a).end()#define rALL(a) (a).rbegin(), (a).rend()#define INF ((1LL << 62) - (1LL << 31))ll LCS(string s, string t) {ll n = s.size(), m = t.size();Graph dp(n, vl(m, 0));rep(i, n) {rep(j, m) {if(i)dp[i][j] = max(dp[i][j], dp[i - 1][j]);if(j)dp[i][j] = max(dp[i][j], dp[i][j - 1]);if(s[i] == t[j]) {if(i && j)dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);elsedp[i][j] = 1;}}}rep(i, n) {// rep(j,m)cout<<dp[i][j]<<" ";// cout<<endl;}return dp[n - 1][m - 1];}template <class Type> size_t LIS(const std::vector<Type> &v) {std::vector<Type> dp;for(const auto &elem : v) {auto it = std::lower_bound(dp.begin(), dp.end(), elem);if(it == dp.end()) {dp.push_back(elem);} else {*it = elem;}}return dp.size();}template <bool Strict, class Type> size_t LIS(const std::vector<Type> &v) {std::vector<Type> dp;auto it = dp.begin();for(const auto &elem : v) {if constexpr(Strict) {it = std::lower_bound(dp.begin(), dp.end(), elem);} else {it = std::upper_bound(dp.begin(), dp.end(), elem);}if(it == dp.end()) {dp.push_back(elem);} else {*it = elem;}}return dp.size();}vector<pair<long long, long long>> prime_factorize(long long N) {// 答えを表す可変長配列vector<pair<long long, long long>> res;// √N まで試し割っていくfor(long long p = 2; p * p <= N; ++p) {// N が p で割り切れないならばスキップif(N % p != 0) {continue;}// N の素因数 p に対する指数を求めるint e = 0;while(N % p == 0) {// 指数を 1 増やす++e;// N を p で割るN /= p;}// 答えに追加res.emplace_back(p, e);}// 素数が最後に残ることがありうるif(N != 1) {res.emplace_back(N, 1);}return res;}vector<long long> divisor(long long n) {vector<long long> ret;for(long long i = 1; i * i <= n; i++) {if(n % i == 0) {ret.push_back(i);if(i * i != n)ret.push_back(n / i);}}sort(ret.begin(), ret.end()); // 昇順に並べるreturn ret;}template <typename T> void print(T &d) {for(auto &i : d)cout << i << " ";if(d.size())cout << endl;}vector<ll> dx = {1, 0, -1, 0};vector<ll> dy = {0, 1, 0, -1};// using mint = modint998244353;using mint = modint1000000007;// using mint = modint;ll MAX = 1e6;vector<mint> fac(MAX + 1, 1);vector<mint> ifac(MAX + 1, 1);mint binomial(ll n, ll k) {if(k < 0 || n < k)return 0;return fac[n] * ifac[n - k] * ifac[k];}void solve() {ll n,m;cin>>n>>m;sl s;s.insert(-1);s.insert(n);s.insert(m-1);priority_queue<P> Q;if(m-1 != 0){Q.push({m-1,0});}if(m-1 != n-1){Q.push({n-m,-n+1});}vl ans(n,-1);ans[m-1] = 1;for(ll i = 2;i<=n;i++){auto [_,x] = Q.top();Q.pop();x*=-1;// cout<<Q.size()<<" qsize "<<x<<endl;ans[x] = i;// print(s);// print(ans);auto itr = s.lower_bound(x);if(*itr - x >1){ll y = (x+*itr)/2;// cout<<Q.size()<<" "<<Q.top().second<<endl;// cout<<"[1] "<<x<<" "<<*itr<<" "<<y<<endl;Q.push({min(y-x,*itr-y),-y});// cout<<Q.size()<<" "<<Q.top().second<<endl;}itr--;if(x - *itr > 1){ll y = (x+*itr)/2;// cout<<"[2] "<<x<<" "<<*itr<<" "<<y<<endl;Q.push({min(y-*itr,x-y),-y});}s.insert(x);}print(ans);}int main() {// { // 前処理 MAX=1e6// rep1(i, MAX) fac[i] = i * fac[i - 1];// ifac[MAX] = fac[MAX].inv();// for(ll i = MAX; i >= 1; i--)// ifac[i - 1] = ifac[i] * (i);// }ll t;// t = 1;cin >> t;rep(_, t) solve();}