Submission #217163

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
217163	2020-03-29 07:10:49	rama_pang	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	67 ms	504 KiB

chameleon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> edges; // edges(a, b) if Query({a, b}) = 1
void FindEdges(vector<int> candidates, int n) { // find edges from one of vertices in candidates to i
  int lo = 0, hi = (int) candidates.size() - 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    vector<int> q(begin(candidates), begin(candidates) + mid + 1);
    q.emplace_back(n);
    if (Query(q) < q.size()) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  edges.emplace_back(candidates[hi], n); // set(candidates[1...hi] + n) has an edge while set(candidates[1...hi-1] + n) doesn't, means there is an edge between candidates[hi] and n
  vector<int> new_candidates(begin(candidates) + hi + 1, end(candidates));  
  vector<int> q(new_candidates); 
  q.emplace_back(n);
  if (Query(q) < q.size()) { // there is an edge between new_candidates and n
    return FindEdges(new_candidates, n);
  }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

chameleon.cpp: In function 'void FindEdges(std::vector<int>, int)':
chameleon.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (Query(q) < q.size()) {
         ~~~~~~~~~^~~~~~~~~~
chameleon.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (Query(q) < q.size()) { // there is an edge between new_candidates and n
       ~~~~~~~~~^~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (Query(q) < q.size()) { // there is an edge between ind[j] and i
           ~~~~~~~~~^~~~~~~~~~

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