#978291 (C++17) No.2740 Old Maid

• 問題: No.2740 Old Maid
• ユーザー: tnakao0123
• 提出日時: 2024-05-01 10:23:16
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 157 ms / 2,000 ms
• コード長: 1,370 bytes
• コンパイル時間: 577 ms
• コンパイル使用メモリ: 57,984 KB
• 最終ジャッジ日時: 2025-02-21 09:59:12
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 62

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:46:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   46 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
main.cpp:47:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |   for (int i = 0; i < n; i++) scanf("%d", ps + i);
      |                               ~~~~~^~~~~~~~~~~~~~

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/* -*- coding: utf-8 -*-
 *
 * 2740.cc:  No.2740 Old Maid - yukicoder
 */
#include<cstdio>
#include<set>
#include<algorithm>
#include<utility>
 
using namespace std;
/* constant */
const int MAX_N = 200000;
/* typedef */
typedef pair<int,int> pii;
typedef set<pii> spii;
struct Node {
  int v, i;
  Node *prv, *nxt;
  Node(): v(), i(), prv(), nxt() {}
  Node(int _v, int _i): v(_v), i(_i), prv(), nxt() {}
  void remove() {
    if (prv != nullptr) prv->nxt = nxt;
    if (nxt != nullptr) nxt->prv = prv;
    prv = nxt = nullptr;
  }
};
/* global variables */
int ps[MAX_N], qs[MAX_N];
Node as[MAX_N];
/* subroutines */
/* main */
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", ps + i);
  spii ss;
  for (int i = 0; i < n; i++) {
    as[i].v = ps[i], as[i].i = i;
    if (i > 0) as[i].prv = &as[i - 1];
    if (i + 1 < n) as[i].nxt = &as[i + 1];
    ss.insert({ps[i], i});
  }
  int m = 0;
  for (int i = 0; i < n; i += 2) {
    int j = ss.begin()->second;
    ss.erase(ss.begin());
    if (as[j].nxt == nullptr) {
      j = ss.begin()->second;
      ss.erase(ss.begin());
    }
    ss.erase({as[j].nxt->v, as[j].nxt->i});
    qs[m++] = as[j].v, qs[m++] = as[j].nxt->v;
    as[j].nxt->remove();
    as[j].remove();
  }
  for (int i = 0; i < n; i++)
    printf("%d%c", qs[i], (i + 1 < n) ? ' ' : '\n');
  
  return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX