結果
問題 |
No.2771 Personal Space
|
ユーザー |
![]() |
提出日時 | 2024-06-15 23:13:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 1,262 bytes |
コンパイル時間 | 692 ms |
コンパイル使用メモリ | 60,136 KB |
最終ジャッジ日時 | 2025-02-21 23:00:03 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:38:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | scanf("%d", &tn); | ~~~~~^~~~~~~~~~~ main.cpp:42:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 42 | scanf("%d%d", &n, &m), m--; | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 2771.cc: No.2771 Personal Space - yukicoder */ #include<cstdio> #include<queue> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 300000; /* typedef */ struct Range { int d, l, r; Range() {} Range(int _l, int _r): d((_r - _l + 1) / 2), l(_l), r(_r) {} bool operator<(const Range &e) const { return d < e.d || (d == e.d && l > e.l); } }; /* global variables */ int ps[MAX_N]; /* subroutines */ /* main */ int main() { int tn; scanf("%d", &tn); while (tn--) { int n, m; scanf("%d%d", &n, &m), m--; fill(ps, ps + n, -1); ps[m] = 0; int ld = m, rd = n - 1 - m; priority_queue<Range> q; for (int i = 1; i < n; i++) { Range e = (! q.empty()) ? q.top() : Range(-1, -1); if (ld >= max(e.d, rd)) { ps[0] = i; ld = 0; if (m > 1) q.push(Range(1, m)); } else if (e.d >= rd) { q.pop(); int x = e.l - 1 + e.d; ps[x] = i; if (e.l < x) q.push(Range(e.l, x)); if (x + 1 < e.r) q.push(Range(x + 1, e.r)); } else { ps[n - 1] = i; rd = 0; if (n - 1 > m + 1) q.push(Range(m + 1, n - 1)); } } for (int i = 0; i < n; i++) printf("%d%c", ps[i] + 1, (i + 1 < n) ? ' ' : '\n'); } return 0; }