#246637 (C++11（廃止可能性あり）) No.670 log は定数

• 問題: No.670 log は定数
• ユーザー: hiyokko2
• 提出日時: 2018-03-24 00:20:37
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: MLE
• 実行時間: -
• コード長: 2,579 bytes
• コンパイル時間: 1,034 ms
• コンパイル使用メモリ: 91,348 KB
• 実行使用メモリ: 792,684 KB
• 最終ジャッジ日時: 2024-06-25 01:06:05
• 合計ジャッジ時間: 11,501 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	MLE * 1 -- * 9

ソースコード

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
// typedef long long ll;
using ll = long long;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
 
using ull = unsigned long long;
ull seed;
int next() {
    seed = seed ^ (seed << 13);
    seed = seed ^ (seed >> 7);
    seed = seed ^ (seed << 17);
    return (seed >> 33);
}
// int qa[];
signed main()
{
  int n, q;
  cin >> n >> q >> seed;
  for (int i = 0; i < 10000; i++) next();
  
  vector<int> a(n);
  for (int i = 0; i < n; i++) a[i] = next();
  // set<int> se;
  // int num[1000];
  // REP(i,n) {
  //   if (i != 0) {
  //     printf("a[%lld] = %lld (%lld)\n", i, a[i], a[i] - a[i - 1]);
  //   }
  //   se.insert(a[i]);
  //   num[a[i] / 10000000]++;
  // }
  // printf("size = %lld\n", se.size());
  // REP(i,100) {
  //   printf("num[%lld] = %lld\n", i, num[i]);
  // }
  sort(a.begin(), a.end());
  ll sm = 0;
  map<int, int> ma;
  vector<pair<int, int>> qa(q);
  for (int i = 0; i < q; i++) {
      // int x = next();
      qa[i].first = next();
      qa[i].second = i;
      // ma[]
      // int cnt = 0;
      // for (int j = 0; j < n; j++) {
      //     if (a[j] < x) cnt++;
      // }
      // int cnt = lower_bound(a.begin(), a.end(), x) - a.begin();
      // sm ^= ll(cnt) * i;
  }
  sort(qa.begin(), qa.end());
  map<int, pair<int, int>> ans;
  int ai = 0, qi = 0;
  int cnt = 0;
  // while (a[ai] < qa[qi]) {
  while (true) {
    if (qa.size() <= qi) {
      break;
    }
    if (a[ai] < qa[qi].first) {
      cnt++;
      ai++;
    } else if (a[ai] == qa[qi].first) {
      ans[qa[qi].first] = make_pair(cnt, qa[qi].second);
      cnt++;
      qi++;
      ai++;
    } else if (a[ai] > qa[qi].first) {
      qi++;
    }
  }
  for (int i = 0; i < q; i++) {
      // int x = next();
      //qa[i] = next();
      // int cnt = 0;
      // for (int j = 0; j < n; j++) {
      //     if (a[j] < x) cnt++;
      // }
      // int cnt = lower_bound(a.begin(), a.end(), x) - a.begin();
      int cnt = ans[qa[i].first].first;
      // sm ^= ll(cnt) * i;
      sm ^= ll(cnt) * qa[i].second;
  }
  cout << sm << endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX