oj.uz

Submission #799965

# Submission time Handle Problem Language Result Execution time Memory
799965 2023-08-01T08:56:08 Z 이성호(#10083) Chameleon's Love (JOI20_chameleon) C++17
24 / 100
 39 ms 1372 KB 
#include "chameleon.h"
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
vector<int> adj[1005];
bool visited[1005];
bool like[1005][1005];
bool found[1005];
void Solve(int N)
{
  for (int i = 2; i <= 2 * N; i++) {
    //1~i-1 사이에 생길 수 있는 변
    vector<int> div[2];
    fill(visited, visited + 1005, false);
    function<void(int, int)> dfs = [&](int v, int id)
    {
      visited[v] = true;
      div[id].push_back(v);
      for (int i:adj[v]) {
        if (!visited[i]) dfs(i, 1 - id);
      }
    };
    int id = 0;
    for (int j = 1; j <= i - 1; j++) {
      if (!visited[j]) {
        dfs(j, id);
        id = !id;
      }
    }
    for (int k = 0; k < 2; k++) {
      while (!div[k].empty()) {
        vector<int> tmp = div[k]; tmp.push_back(i);
        if (Query(tmp) != tmp.size()) {
          vector<int> cand = div[k];
          while (cand.size() > 1) {
            vector<int> mid;
            for (int p = 0; p < (int)cand.size() / 2; p++) mid.push_back(cand[p]);
            mid.push_back(i);
            if (Query(mid) != mid.size()) {
              mid.pop_back();
              cand = mid;
            }
            else {
              mid.clear();
              for (int p = (int)cand.size() / 2; p < (int)cand.size(); p++) mid.push_back(cand[p]);
              cand = mid;
            }
          }
          int res = cand[0];
          adj[res].push_back(i);
          adj[i].push_back(res);
          div[k].erase(remove(div[k].begin(), div[k].end(), res), div[k].end());
        }
        else break;
      }
    }
  }
  for (int i = 1; i <= 2 * N; i++) {
    if (found[i]) continue;
    if (adj[i].size() == 1) {
      Answer(i, adj[i][0]);
      found[i] = found[adj[i][0]] = true;
    }
    else {
      assert(adj[i].size() == 3);
      for (int k = 0; k < 3; k++) {
        vector<int> tmp;
        for (int j = 0; j < 3; j++) {
          if (k != j) tmp.push_back(adj[i][j]);
        }
        tmp.push_back(i);
        if (Query(tmp) == 1) {
          like[i][adj[i][k]] = true;
        }
      }
    }
  }
  for (int i = 1; i <= 2 * N; i++) {
    if (found[i]) continue;
    for (int k:adj[i]) {
      if (!like[i][k] && !like[k][i]) {
        Answer(i, k);
        found[i] = found[k] = true;
        break;
      }
    }
  }
}

Compilation message

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:36:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if (Query(tmp) != tmp.size()) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:42:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if (Query(mid) != mid.size()) {
      |                 ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 15 ms 420 KB Output is correct
4 Correct 15 ms 336 KB Output is correct
5 Correct 15 ms 336 KB Output is correct
6 Correct 19 ms 336 KB Output is correct
7 Correct 15 ms 416 KB Output is correct
8 Correct 15 ms 396 KB Output is correct
9 Correct 15 ms 400 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Wrong Answer [5]
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 39 ms 1372 KB Wrong Answer [5]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 15 ms 420 KB Output is correct
4 Correct 15 ms 336 KB Output is correct
5 Correct 15 ms 336 KB Output is correct
6 Correct 19 ms 336 KB Output is correct
7 Correct 15 ms 416 KB Output is correct
8 Correct 15 ms 396 KB Output is correct
9 Correct 15 ms 400 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 0 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 0 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Incorrect 1 ms 336 KB Wrong Answer [5]
22 Halted 0 ms 0 KB -