제출 #251496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251496		imeimi2000	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	74 ms	512 KiB

chameleon

#ifdef imeimi

#include <vector>

void Solve(int N);

int Query(const std::vector<int> &p);
void Answer(int a, int b);

#include <cstdio>
#include <cstdlib>

namespace {

using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;

constexpr int Q_MAX = 20'000;
constexpr int N_MAX = 500;

int N;
int Y[N_MAX * 2 + 1], C[N_MAX * 2 + 1], L[N_MAX * 2 + 1];

int query_count = 0;
int answer_count = 0;
bool finishes[N_MAX * 2 + 1];

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}

}  // namespace

int Query(const std::vector<int> &p) {
  if (++query_count > Q_MAX);// WrongAnswer(3);
  bool presents[N_MAX * 2 + 1];
  for (int i = 1; i <= N * 2; ++i) presents[i] = false;
  for (const int k : p) {
    if (k <= 0 || k > N * 2) WrongAnswer(1);
    if (presents[k]) WrongAnswer(2);
    presents[k] = true;
  }
  bool colors[N_MAX + 1];
  for (int j = 1; j <= N; ++j) colors[j] = false;
  int color_count = 0;
  for (int i = 1; i <= N * 2; ++i) {
    if (!presents[i]) continue;
    const int color = presents[L[i]] ? C[L[i]] : C[i];
    if (!colors[color]) {
      ++color_count;
      colors[color] = true;
    }
  }
  return color_count;
}

void Answer(int a, int b) {
  ++answer_count;
  if (a <= 0 || a > N * 2) WrongAnswer(4);
  if (b <= 0 || b > N * 2) WrongAnswer(4);
  if (finishes[a]) WrongAnswer(5);
  finishes[a] = true;
  if (finishes[b]) WrongAnswer(5);
  finishes[b] = true;
  if (C[a] != C[b]) WrongAnswer(6);
}

int main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  for (int i = 1; i <= N * 2; ++i) {
    if (scanf("%d", &Y[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 1; i <= N * 2; ++i) {
    if (scanf("%d", &C[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 1; i <= N * 2; ++i) {
    if (scanf("%d", &L[i]) != 1) {
      fprintf(stderr, "Error while reading input.\n");
      exit(1);
    }
  }
  for (int i = 1; i <= N * 2; ++i) finishes[i] = false;
  Solve(N);
  if (answer_count != N) WrongAnswer(7);
  printf("Accepted: %d\n", query_count);
  return 0;
}

#else

#include "chameleon.h"

#endif

#include <bits/stdc++.h>

using namespace std;

int ord[1001], in[1001], out[1001];
vector<int> edge[1001];

void dfs(int x) {
    for (int i : edge[x]) {
        if (ord[i] != -1) continue;
        ord[i] = ord[x] ^ 1;
        dfs(i);
    }
}

int get_edge(const vector<int> &G, int s, int e, int x, bool c) {
    if (s > e) return 0;
    vector<int> q(1, x);
    for (int i = s; i <= e; ++i) q.push_back(G[i]);
    if (!c && Query(q) == int(q.size())) return 0;
    if (s == e) return G[s];
    int m = (s + e) / 2;
    int ret = get_edge(G, s, m, x, 0);
    if (ret) return ret;
    return get_edge(G, m + 1, e, x, 1);
}

void Solve(int n) {
    for (int i = 2; i <= n + n; ++i) {
        memset(ord, -1, sizeof(ord));
        for (int j = 1; j < i; ++j) {
            if (ord[j] != -1) continue;
            ord[j] = 0;
            dfs(j);
        }
        vector<int> G[2];
        for (int j = 1; j < i; ++j) G[ord[j]].push_back(j);
        for (int it = 0; it < 2; ++it) {
            for (int j; j = get_edge(G[it], 0, int(G[it].size()) - 1, i, 0); ) {
                G[it].erase(find(G[it].begin(), G[it].end(), j));
                edge[i].push_back(j);
                edge[j].push_back(i);
            }
        }
    }
    memset(ord, 0, sizeof(ord));
    for (int i = 1; i <= n + n; ++i) {
        if (int(edge[i].size()) == 1) {
            if (ord[i]) continue;
            Answer(i, edge[i][0]);
            ord[i] = ord[edge[i][0]] = 1;
            continue;
        }
        for (int j = 0; j < 3; ++j) {
            if (Query({ i, edge[i][(j + 1) % 3], edge[i][(j + 2) % 3] }) == 1) {
                out[i] = edge[i][j];
                break;
            }
        }
        in[out[i]] = i;
    }
    for (int i = 1; i <= n + n; ++i) {
        if (ord[i]) continue;
        for (int j : edge[i]) {
            if (j == in[i] || j == out[i]) continue;
            Answer(i, j);
            ord[i] = ord[j] = 1;
            break;
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:145:27: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
             for (int j; j = get_edge(G[it], 0, int(G[it].size()) - 1, i, 0); ) {
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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