oj.uz

Submission #212049

# Submission time Handle Problem Language Result Execution time Memory
212049 2020-03-22T07:13:47 Z extraterrestrial Chameleon's Love (JOI20_chameleon) C++14
44 / 100
 101 ms 516 KB 
#include "chameleon.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll

mt19937 rnd(239);

void dfs(int v, int cl, vector<vector<int>> &g, vector<int> &color, vector<bool> &used) {
  used[v] = true;
  color[v] = cl;
  for (auto u : g[v]) {
    if (!used[u]) {
      dfs(u, cl ^ 1, g, color, used);
    }
  }
}

void Solve(int n) {
  vector<vector<int>> g(2 * n + 1);
  vector<int> color(2 * n + 1);
  vector<bool> used(2 * n + 1);
  vector<pair<int, int>> interesting;
  for (int i = 2; i <= 2 * n; i++) {
    fill(all(used), false);
    for (int j = 1; j < i; j++) {
      if (!used[j]) {
        dfs(j, 0, g, color, used);
      }
    }
    vector<int> have0, have1;
    for (int j = 1; j < i; j++) {
      if (color[j] == 0) {
        have0.pb(j);
      }
      else {
        have1.pb(j);
      }
    }
    int cur = 0;
    while (cur < SZ(have0)) {
      int l = cur - 1, r = SZ(have0);
      while (r - l > 1) {
        int mid = (l + r) / 2;
        vector<int> kek;
        for (int j = cur; j <= mid; j++) {
          kek.pb(have0[j]);
        }
        kek.pb(i);
        if (Query(kek) < SZ(kek)) {
          r = mid;
        }
        else {
          l = mid;
        }
      }
      if (r < SZ(have0)) {
        int v = have0[r];
        interesting.pb({v, i});
        g[v].pb(i);
        g[i].pb(v);
        cur = r + 1;
      }
      else {
        break;
      }
    }
    cur = 0;
    while (cur < SZ(have1)) {
      int l = cur - 1, r = SZ(have1);
      while (r - l > 1) {
        int mid = (l + r) / 2;
        vector<int> kek;
        for (int j = cur; j <= mid; j++) {
          kek.pb(have1[j]);
        }
        kek.pb(i);
        if (Query(kek) < SZ(kek)) {
          r = mid;
        }
        else {
          l = mid;
        }
      }
      if (r < SZ(have1)) {
        int v = have1[r];
        interesting.pb({v, i});
        g[v].pb(i);
        g[i].pb(v);
        cur = r + 1;
      }
      else {
        break;
      } 
    }
  }
  /*for (auto it : interesting) {
    cerr << it.F << ' ' << it.S << '\n';
  }*/
  vector<pair<int, int>> rez;
  for (auto it : interesting) {
    vector<int> kek;
    for (int i = 1; i <= 2 * n; i++) {
      if (i != it.F && i != it.S) {
        kek.pb(i);
      }
    }
    if (Query(kek) < n) {
      //cerr << it.F << ' ' << it.S << '\n';
      rez.pb(it);
    }
  }
  for (auto it : rez) {
    Answer(it.F, it.S);
  }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 98 ms 504 KB Output is correct
4 Correct 99 ms 384 KB Output is correct
5 Correct 97 ms 448 KB Output is correct
6 Correct 99 ms 384 KB Output is correct
7 Correct 97 ms 516 KB Output is correct
8 Correct 101 ms 384 KB Output is correct
9 Correct 101 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 6 ms 256 KB Output is correct
18 Correct 6 ms 384 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 84 ms 508 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 98 ms 504 KB Output is correct
4 Correct 99 ms 384 KB Output is correct
5 Correct 97 ms 448 KB Output is correct
6 Correct 99 ms 384 KB Output is correct
7 Correct 97 ms 516 KB Output is correct
8 Correct 101 ms 384 KB Output is correct
9 Correct 101 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 7 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 7 ms 384 KB Output is correct
24 Correct 6 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 6 ms 256 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Incorrect 84 ms 508 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -