Submission #1307369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307369		KickingKun	Chameleon's Love (JOI20_chameleon)	C++20	40 / 100	17 ms	440 KiB

chameleon

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

using namespace std;

namespace {

int variable_example = 1;

}  // namespace

vector <int> adj[1001];
int c[1001];

void dfs(int u, int color) {
  c[u] = color;
  for (int v: adj[u]) if (c[v] == -1) {
    dfs(v, 1 - color);
  }
}

bool haveEdge(int x, int y) {
  return find(adj[x].begin(), adj[x].end(), y) != adj[x].end();
}

void Solve(int N) {
  for (int i = 1; i <= 2 * N; i++) {
    adj[i].clear(); c[i] = -1;
  }

  for (int i = 1; i <= 2 * N; i++) {
    for (int j = i + 1; j <= 2 * N; j++) {
      if (Query({i, j}) == 1) {
        // i va j cung mau
        // i thich j / j thich i
        adj[i].emplace_back(j);
        adj[j].emplace_back(i);
      }
    }
  }

  for (int i = 1; i <= 2 * N; i++) 
    if (c[i] == -1) dfs(i, 0);

  for (int i = 1; i <= 2 * N; i++) {
    if (adj[i].size() == 3) {
      int x = adj[i][0], y = adj[i][1], z = adj[i][2];
      int crush;

      if (Query({i, x, y}) == 1) {
        crush = z;
      }
      else if (Query({i, x, z}) == 1) {
        crush = y;
      }
      else {
        crush = x;
      }

      adj[i].erase(find(adj[i].begin(), adj[i].end(), crush));
      // cerr << i << " like " << crush << endl;
    }
  }

  for (int i = 1; i <= 2 * N; i++) if (c[i] == 0) {
    if (adj[i].size() == 1) Answer(i, adj[i][0]);
    else {
      int x = adj[i][0], y = adj[i][1];
      if (haveEdge(x, i)) Answer(i, x);
      else Answer(i, y);
    }
  }
}

• Subtask 1: 0 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36