oj.uz

Submission #38946

# Submission time Handle Problem Language Result Execution time Memory
38946 2018-01-08T09:33:18 Z funcsr None (JOI16_memory2) C++14
100 / 100
 0 ms 2064 KB 
#include "Memory2_lib.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <cassert>
#include <random>
#include <map>
#include <ctime>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
#define MOD 1000000007

mt19937 mt_rand(time(NULL));
vector<int> G[50];
bool used[50];
int A[100];

int cache[100][100];
int query(int a, int b) {
  if (cache[a][b] != -1) return cache[a][b];
  assert(a != b);
  return cache[a][b] = cache[b][a] = Flip(a, b);
}

void Solve(int T, int N) {
  if (N == 1) return Answer(0, 1, 0);
  rep(i, 2*N) A[i] = -1;
  rep(i, 2*N) rep(j, 2*N) cache[i][j] = -1;
  vector<int> S;
  rep(i, 2*N) {
    S.pb(i);
    if (S.size() == 4) {
      int mi = -1, v = -1;
      rep(i, 4) {
        vector<int> values;
        rep(j, 4) if (i != j) values.pb(query(S[i], S[j]));
        sort(all(values));
        uniq(values);
        if (values.size() == 1) mi = i, v = values[0];
      }
      assert(mi != -1);
      A[S[mi]] = v;
      S.erase(S.begin()+mi);
    }
  }
  assert(S.size() == 3);
  rep(i, 3) {
    vector<int> values;
    rep(j, 3) if (i != j) values.pb(query(S[i], S[j]));
    sort(all(values));
    uniq(values);
    if (values.size() == 1) {
      A[S[i]] = values[0];
      S.erase(S.begin()+i);
      break;
    }
  }
  assert(S.size() == 2);
  rep(i, 2*N) if (A[i] != -1) used[A[i]] = true;
  int unused = -1;
  rep(i, N) if (!used[i]) unused = i;
  A[S[0]] = A[S[1]] = unused;

  rep(i, 2*N) G[A[i]].pb(i);
  rep(i, N) assert(G[i].size() == 2);
  rep(i, N) Answer(G[i][0], G[i][1], i);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2064 KB Output is correct
2 Correct 0 ms 2064 KB Output is correct
3 Correct 0 ms 2064 KB Output is correct
4 Correct 0 ms 2064 KB Output is correct
5 Correct 0 ms 2064 KB Output is correct
6 Correct 0 ms 2064 KB Output is correct
7 Correct 0 ms 2064 KB Output is correct
8 Correct 0 ms 2064 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2064 KB Output is correct
2 Correct 0 ms 2064 KB Output is correct
3 Correct 0 ms 2064 KB Output is correct
4 Correct 0 ms 2064 KB Output is correct
5 Correct 0 ms 2064 KB Output is correct
6 Correct 0 ms 2064 KB Output is correct
7 Correct 0 ms 2064 KB Output is correct
8 Correct 0 ms 2064 KB Output is correct
9 Correct 0 ms 2064 KB Output is correct
10 Correct 0 ms 2064 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2064 KB Output is correct
2 Correct 0 ms 2064 KB Output is correct
3 Correct 0 ms 2064 KB Output is correct
4 Correct 0 ms 2064 KB Output is correct
5 Correct 0 ms 2064 KB Output is correct
6 Correct 0 ms 2064 KB Output is correct
7 Correct 0 ms 2064 KB Output is correct
8 Correct 0 ms 2064 KB Output is correct
9 Correct 0 ms 2064 KB Output is correct
10 Correct 0 ms 2064 KB Output is correct