oj.uz

Submission #799886

# Submission time Handle Problem Language Result Execution time Memory
799886 2023-08-01T07:33:27 Z 이성호(#10083) Chameleon's Love (JOI20_chameleon) C++17
4 / 100
 39 ms 840 KB 
#include "chameleon.h"
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
namespace {

}  // namespace

int id[1005];
bool done[1005], found[1005];
bool like[1005][1005];
vector<int> tri[1005];

int query(vector<int> &v)
{
  vector<int> vc;
  for (int i:v) vc.push_back(id[i]);
  return Query(vc);
}

void answer(int u, int v)
{
  Answer(id[u], id[v]);
}

void Solve(int N) {
  vector<int> gen1;
  vector<int> gen2;
  for (int i = 1; i <= 2 * N; i++) {
    gen1.push_back(i);
    if (Query(gen1) < gen1.size()) {
      gen1.pop_back();
      gen2.push_back(i);
    }
  }
  assert(gen1.size() == N);
  assert(gen2.size() == N);
  for (int i = 1; i <= N; i++) id[i] = gen1[i-1];
  for (int i = N+1; i <= 2*N; i++) id[i] = gen2[i-N-1];
  for (int i = 1; i <= N; i++) {
    vector<int> ans;
    fill(done, done + 1005, false);
    for (int j = 0; j < 3; j++) {
      vector<int> cand;
      for (int j = N + 1; j <= 2 * N; j++) {
        if (!done[j]) cand.push_back(j);
      }
      if (cand.empty()) break;
      while (cand.size() >= 2) {
        vector<int> tmp;
        for (int j = 0; j < (int)cand.size() / 2; j++) {
          tmp.push_back(cand[j]);
        }
        tmp.push_back(i);
        if (query(tmp) != tmp.size()) {
          tmp.clear();
          for (int j = 0; j < (int)cand.size() / 2; j++) {
            tmp.push_back(cand[j]);
          }
          cand = tmp;
        }
        else {
          tmp.clear();
          for (int j = (int)cand.size() / 2; j < (int)cand.size(); j++) {
            tmp.push_back(cand[j]);
          }
          cand = tmp;
        }
      }
      int res = cand[0];
      vector<int> tmp; tmp.push_back(res); tmp.push_back(i);
      if (query(tmp) != 1) {
        done[res] = true;
      }
      else {
        ans.push_back(res);
        done[res] = true;
      }
    }
    if (ans.size() == 1) {
      answer(i, ans[0]);
      found[i] = found[ans[0]] = true;
    }
    else {
      assert(ans.size() == 3);
      tri[i] = ans;
      for (int k = 0; k < 3; k++) {
        vector<int> tmp(1, i);
        for (int j = 0; j < 3; j++) {
          if (k != j) tmp.push_back(ans[j]);
        }
        if (query(tmp) == 1) {
          like[i][ans[k]] = true;
        }
      }
    }
  }
  for (int i = N + 1; i <= 2 * N; i++) {
    if (found[i]) continue;
    vector<int> ans;
    fill(done, done + 1005, false);
    for (int j = 0; j < 3; j++) {
      vector<int> cand;
      for (int j = 1; j <= N; j++) {
        if (!done[j]) cand.push_back(j);
      }
      if (cand.empty()) break;
      while (cand.size() >= 2) {
        vector<int> tmp;
        for (int j = 0; j < (int)cand.size() / 2; j++) {
          tmp.push_back(cand[j]);
        }
        tmp.push_back(i);
        if (query(tmp) != tmp.size()) {
          tmp.clear();
          for (int j = 0; j < (int)cand.size() / 2; j++) {
            tmp.push_back(cand[j]);
          }
          cand = tmp;
        }
        else {
          tmp.clear();
          for (int j = (int)cand.size() / 2; j < (int)cand.size(); j++) {
            tmp.push_back(cand[j]);
          }
          cand = tmp;
        }
      }
      int res = cand[0];
      vector<int> tmp; tmp.push_back(res); tmp.push_back(i);
      if (query(tmp) != 1) {
        done[res] = true;
      }
      else {
        ans.push_back(res);
        done[res] = true;
      }
    }
    if (ans.size() == 1) {
      assert(!found[ans[0]]);
      answer(i, ans[0]);
      found[i] = found[ans[0]] = true;
    }
    else {
      assert(ans.size() == 3);
      tri[i] = ans;
      for (int k = 0; k < 3; k++) {
        vector<int> tmp(1, i);
        for (int j = 0; j < 3; j++) {
          if (k != j) tmp.push_back(ans[j]);
        }
        if (query(tmp) == 1) {
          like[i][ans[k]] = true;
        }
      }
    }
  }
  for (int i = 1; i <= 2 * N; i++) {
    if (!found[i]) {
      int res = -1;
      for (int k = 0; k < 3; k++) {
        if (like[i][tri[i][k]] || like[tri[i][k]][i]) continue;
        res = tri[i][k];
      }
      found[i] = found[res] = true;
      answer(i, res);
    }
  }
  return;
}

Compilation message

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if (Query(gen1) < gen1.size()) {
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from chameleon.cpp:3:
chameleon.cpp:37:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   assert(gen1.size() == N);
      |          ~~~~~~~~~~~~^~~~
chameleon.cpp:38:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   assert(gen2.size() == N);
      |          ~~~~~~~~~~~~^~~~
chameleon.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (query(tmp) != tmp.size()) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:115:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         if (query(tmp) != tmp.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 26 ms 336 KB Output is correct
4 Correct 25 ms 336 KB Output is correct
5 Correct 39 ms 336 KB Output is correct
6 Correct 35 ms 344 KB Output is correct
7 Correct 26 ms 360 KB Output is correct
8 Correct 39 ms 336 KB Output is correct
9 Correct 25 ms 336 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Runtime error 1 ms 464 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Runtime error 1 ms 464 KB Execution killed with signal 6
5 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 29 ms 840 KB Wrong Answer [3]
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 26 ms 336 KB Output is correct
4 Correct 25 ms 336 KB Output is correct
5 Correct 39 ms 336 KB Output is correct
6 Correct 35 ms 344 KB Output is correct
7 Correct 26 ms 360 KB Output is correct
8 Correct 39 ms 336 KB Output is correct
9 Correct 25 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Runtime error 1 ms 464 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -