oj.uz

답안 #251494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251494 2020-07-21T13:31:39 Z imeimi2000 카멜레온의 사랑 (JOI20_chameleon) C++17
20 / 100
 62 ms 384 KB 
#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) {
    if (s > e) return 0;
    vector<int> q(1, x);
    for (int i = s; i <= e; ++i) q.push_back(G[i]);
    if (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);
    if (ret) return ret;
    return get_edge(G, m + 1, e, x);
}

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[i] != -1) continue;
            ord[i] = 0;
            dfs(i);
        }
        vector<int> G[2];
        for (int j = 1; j < i; ++j) G[ord[i]].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); ) {
                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 (ord[i]) continue;
        if (int(edge[i].size()) == 1) {
            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;
        }
    }
}

Compilation message

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); ) {
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 33 ms 384 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Incorrect 4 ms 384 KB Wrong Answer [5]
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 62 ms 384 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 33 ms 384 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -