Submission #234857

#TimeUsernameProblemLanguageResultExecution timeMemory
234857anaykChameleon's Love (JOI20_chameleon)C++14
40 / 100
51 ms504 KiB
#include "chameleon.h" #include <set> #include <vector> std::set<int> Adj[1001]; std::vector<int> edges[1001]; std::vector<int> groups[4]; int part[1001]; int check(int x, int y) { return (y != x + 1); } int threeQuery(int x, int y, int z) { std::vector<int> q; q.push_back(x); q.push_back(y); q.push_back(z); return Query(q); } int queryRange(int l, int r, int group) { if(l == r) return 1; std::vector<int> q; for(int i = l; i <= r; i++) q.push_back(groups[group][i]); return Query(q); } int queryRange(int l, int r, int x, int group) { std::vector<int> q; for(int i = l; i <= r; i++) q.push_back(groups[group][i]); q.push_back(x); return Query(q); } void bs(int x, int l, int r, int group) { if(l == r) { Adj[x].insert(groups[group][l]); Adj[groups[group][l]].insert(x); return; } int m = (l+r)/2; if(check(queryRange(l, m, group), queryRange(l, m, x, group))) bs(x, l, m, group); if(check(queryRange(m+1, r, group), queryRange(m+1, r, x, group))) bs(x, m+1, r, group); } void Solve(int N) { for(int i = 0; i < 4; i++) { groups[i].push_back(i+1); part[i+1] = i; } for(int i = 5; i <= 2*N; i++) { for(int j = 0; j < 4; j++) { groups[j].push_back(i); if(Query(groups[j]) == groups[j].size()) { part[i] = j; break; } else groups[j].pop_back(); } } for(int i = 1; i <= 2*N; i++) { for(int j = part[i]+1; j < 4; j++) { if(check(queryRange(0, groups[j].size()-1, j), queryRange(0, groups[j].size()-1, i, j))) bs(i, 0, groups[j].size()-1, j); } } for(int i = 1; i <= 2*N; i++) { if(Adj[i].size() == 3) { for(std::set<int>::iterator it = Adj[i].begin(); it != Adj[i].end(); it++) { edges[i].push_back(*it); } } } for(int i = 1; i <= 2*N; i++) { if(edges[i].size() == 3) { int x0 = threeQuery(i, edges[i][1], edges[i][2]); int x1 = threeQuery(i, edges[i][0], edges[i][2]); int x; if(x0 == 1) x = edges[i][0]; else if(x1 == 1) x = edges[i][1]; else x = edges[i][2]; Adj[x].erase(i); Adj[i].erase(x); } } for(int i = 1; i <= 2*N; i++) { int j = *Adj[i].begin(); if(i < j) Answer(i, j); } }

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(Query(groups[j]) == groups[j].size()) {
          ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...