Submission #211905

#	Time	Username	Problem	Language	Result	Execution time	Memory
211905		mieszko11b	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	73 ms	512 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

namespace {
	int cnt = 0;
	vector<int> A[4];
	vector<int> E[1007];
	int nxt[1007], prv[1007];
}  // namespace

bool check(int i, int a, int b, int w) {
	vector<int> V(b - a + 1);
	for(int j = a ; j <= b ; j++)
		V[j - a] = A[i][j];
	V.push_back(w);
	return Query(V) != V.size();
}

void Solve(int n) {
	n *= 2;
	
	for(int i = 1 ; i <= n ; i++) {
		int firstok = -1;
		for(int j = 0 ; j < cnt ; j++) {
			int ind = 0;
			bool ok = true;
			while(ind < A[j].size() && check(j, ind, A[j].size() - 1, i)) {
				ok = false;
				int pocz = ind, kon = A[j].size() - 1, mid;
				while(pocz < kon) {
					mid = (pocz + kon) / 2;
					if(check(j, ind, mid, i))
						kon = mid;
					else
						pocz = mid + 1;
				}
				E[i].push_back(A[j][pocz]);
				E[A[j][pocz]].push_back(i);
				//~ cout << "E " << i << " " << A[j][pocz] << endl;
				ind = pocz + 1;
			}
			if(ok && firstok == -1)
				firstok = j;
		}
		
		if(firstok == -1) {
			firstok = cnt++;
		}
		
		A[firstok].push_back(i);
	}
	
	//~ for(int i = 1 ; i <= n ; i++) {
		//~ cout << i << ": ";
		//~ for(int j : E[i])
			//~ cout << j << " ";
		//~ cout << endl;
	//~ }
	
	for(int i = 1 ; i <= n ; i++) {
		if(E[i].size() == 3) {
			if(Query({i, E[i][0], E[i][1]}) == 1) {
				nxt[i] = E[i][2];
				//~ prv[E[i][2]] = i;
			} else if(Query({i, E[i][0], E[i][2]}) == 1) {
				nxt[i] = E[i][1];
				//~ prv[E[i][1]] = i;
			} else {
				nxt[i] = E[i][0];
				//~ prv[E[i][0]] = i;
			}
		}
	}
	
	for(int i = 1 ; i <= n ; i++) {
		int ans;
		for(int x : E[i])
			if(x != nxt[i] && nxt[x] != i)
				ans = x;
		if(ans > i)
			Answer(i, ans);
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'bool check(int, int, int, int)':
chameleon.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return Query(V) != V.size();
         ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:30:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ind < A[j].size() && check(j, ind, A[j].size() - 1, i)) {
          ~~~~^~~~~~~~~~~~~
chameleon.cpp: At global scope:
chameleon.cpp:11:17: warning: '{anonymous}::prv' defined but not used [-Wunused-variable]
  int nxt[1007], prv[1007];
                 ^~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:84:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
    Answer(i, ans);
    ~~~~~~^~~~~~~~

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