oj.uz

Submission #216650

# Submission time Handle Problem Language Result Execution time Memory
216650 2020-03-27T18:46:35 Z AlexPop28 Chameleon's Love (JOI20_chameleon) C++14
44 / 100
 98 ms 504 KB 
#include <bits/stdc++.h>
#include "chameleon.h"
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

namespace {
int Check(const vector<int> &v, int n, int node) {
  vector<int> u(v.begin(), v.begin() + n + 1);
  u.emplace_back(node);
//  dbg() "query: ";
//  for (int x :  u) dbg() x << ' ';
//  dbg() endl;
  int ans = Query(u);
//  dbg() name(ans) endl;
  return ans;
}
}

void Solve(int n) {
  vector<vector<int>> adj(2 * n + 1);
  vector<vector<int>> sides(2);
  vector<int> col(2 * n + 1);
  
  function<void(int, int)> Split = [&](int node, int c) {
    sides[c].emplace_back(node);
    col[node] = c;
    for (int &x : adj[node]) {
      if (col[x] == -1) {
        Split(x, c ^ 1);
      }
    }
  };

  auto AddEdge = [&](int a, int b) {
    adj[a].emplace_back(b);
    adj[b].emplace_back(a);

    dbg() name(a) name(b) endl;
  };

  for (int i = 1; i <= 2 * n; ++i) {
    sides[0].clear(); sides[1].clear();
    fill(col.begin(), col.end(), -1);
    for (int j = 1; j < i; ++j) {
      if (col[j] == -1) {
        Split(j, 0);
      }
    }

//    dbg() "parts: " << endl;
//    for (int x : sides[0]) dbg() x << ' '; dbg() endl;
//    for (int x : sides[1]) dbg() x << ' '; dbg() endl;
//    dbg() endl;

    for (int side = 0; side < 2; ++side) {
      auto v = sides[side];

//      dbg() name(i) name(side) name(v.size()) endl;
      while (!v.empty()) {
//        dbg() "enter\n";
        int lo = 0, hi = v.size() - 1, ans = -1;
        while (lo <= hi) {
          int mid = lo + (hi - lo) / 2;
          if (Check(v, mid, i) <= mid + 1) {
            hi = mid - 1;
            ans = mid;
          } else {
            lo = mid + 1;
          }
        }
        
        if (ans == -1) break;

        int x = v[ans];
        AddEdge(i, x);
        v = vector<int>(v.begin() + ans + 1, v.end());
      }
    }
  }

  int cnt_ans = 0;
  vector<set<int>> link(2 * n + 1);
  
  auto AddLink = [&](int x, int y) {
    link[x].emplace(y);
    if (link[y].count(x)) {
      ++cnt_ans;
      Answer(x, y);
    }
  };

  for (int i = 1; i <= 2 * n; ++i) {
    if ((int)adj[i].size() == 1) {
      AddLink(i, adj[i][0]);
      continue;
    }
    
    assert((int)adj[i].size() == 3);
    
    int x = Query({i, adj[i][0], adj[i][1]});
    int y = Query({i, adj[i][0], adj[i][2]});
    int z = Query({i, adj[i][1], adj[i][2]});

    assert(x + y + z == 5);

    if (x == 1) {
      AddLink(i, adj[i][0]);
      AddLink(i, adj[i][1]);
    }
    if (y == 1) {
      AddLink(i, adj[i][0]);
      AddLink(i, adj[i][2]);
    }
    if (z == 1) {
      AddLink(i, adj[i][1]);
      AddLink(i, adj[i][2]);
    }
  }
  
  assert(cnt_ans == n);
}

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 87 ms 504 KB Output is correct
4 Correct 87 ms 504 KB Output is correct
5 Correct 89 ms 504 KB Output is correct
6 Correct 88 ms 504 KB Output is correct
7 Correct 88 ms 504 KB Output is correct
8 Correct 94 ms 504 KB Output is correct
9 Correct 88 ms 504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 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 5 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 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 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 5 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 8 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 8 ms 384 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 8 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 8 ms 384 KB Output is correct
17 Correct 8 ms 384 KB Output is correct
18 Correct 8 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 5 ms 384 KB Output is correct
3 Incorrect 98 ms 504 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 87 ms 504 KB Output is correct
4 Correct 87 ms 504 KB Output is correct
5 Correct 89 ms 504 KB Output is correct
6 Correct 88 ms 504 KB Output is correct
7 Correct 88 ms 504 KB Output is correct
8 Correct 94 ms 504 KB Output is correct
9 Correct 88 ms 504 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 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 5 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 8 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 8 ms 384 KB Output is correct
22 Correct 8 ms 384 KB Output is correct
23 Correct 8 ms 384 KB Output is correct
24 Correct 6 ms 384 KB Output is correct
25 Correct 8 ms 384 KB Output is correct
26 Correct 8 ms 384 KB Output is correct
27 Correct 8 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Incorrect 98 ms 504 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -