oj.uz

Submission #799857

# Submission time Handle Problem Language Result Execution time Memory
799857 2023-08-01T07:07:45 Z 이성호(#10083) Chameleon's Love (JOI20_chameleon) C++17
4 / 100
 29 ms 928 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);
    }
  }
  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);
      }
      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) {
        break;
      }
      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);
      }
      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) {
        break;
      }
      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()) {
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if (query(tmp) != tmp.size()) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:111:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         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 1 ms 336 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 18 ms 336 KB Output is correct
5 Correct 18 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Correct 17 ms 360 KB Output is correct
8 Correct 17 ms 364 KB Output is correct
9 Correct 17 ms 364 KB Output is correct

Subtask #2
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 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 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 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 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 29 ms 928 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 1 ms 336 KB Output is correct
3 Correct 20 ms 336 KB Output is correct
4 Correct 18 ms 336 KB Output is correct
5 Correct 18 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Correct 17 ms 360 KB Output is correct
8 Correct 17 ms 364 KB Output is correct
9 Correct 17 ms 364 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 Runtime error 1 ms 464 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -