Submission #209657

#	Time	Username	Problem	Language	Result	Execution time	Memory
209657		EntityIT	Memory 2 (JOI16_memory2)	C++14	100 / 100	6 ms	376 KiB

memory2

#include "Memory2_lib.h"
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

void Solve(int T, int N){
  vector<int> a(N << 1, -1);

  vector<int> rem(N << 1); iota(all(rem), 0);

  while (sz(rem) > 1) {
    int chosen = rem[ (rng() ^ rng() ^ rng() ) % sz(rem)];
    for (const auto &i : rem) if (i ^ chosen) a[i] = Flip(chosen, i);
    a[chosen] = -1;
    for (int i = 0; i < N; ++i) if (count(all(a), i) & 1) {
      a[chosen] = i;
      break ;
    }

    vector<int> nRem;
    for (const auto &i : rem) if (i ^ chosen && a[i] == a[chosen]) nRem.emplace_back(i);
    rem.swap(nRem);
  }

  for (int i = 0; i < N; ++i) {
    int x = (int)(find(all(a), i) - a.begin() ),
        y = (int)(find( (x + 1) + all(a), i) - a.begin() );
    Answer(x, y, i);
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 50 / 50
• Subtask 3: 40 / 40