結果

問題 No.670 log は定数
ユーザー hiyokko2hiyokko2
提出日時 2018-03-24 00:20:37
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0