oj.uz

Submission #245375

# Submission time Handle Problem Language Result Execution time Memory
245375 2020-07-06T07:33:05 Z kostia244 Chameleon's Love (JOI20_chameleon) C++17
24 / 100
 43 ms 564 KB 
#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
vector<int> merge(vector<int> a, vector<int> b) {
	for(auto i : b) a.push_back(i);
	return a;
}
bool add(vector<int> x, vector<int> v) {
	for(auto i : v) x.push_back(i);
	return x.size()<=500 && Query(x) == x.size();
}
vector<int> seg(vector<int> v, int l, int r) {
	vector<int> res;
	while(l <= r) res.push_back(v[l++]);
	return res;
}
vector<int> pref(vector<int> v, int x) {
	return seg(v, 0, x);
}
void Solve(int n) {
	vector<vi> g(2*n+1);
	vi t[4];
	for(int i = 1; i <= 2*n; i++) {
		int x = 0;
		while(x < 3 && !add(t[x], {i})) x++;
		t[x].push_back(i);
	}
	
	for(int i = 4; i-- > 1;) {
		//cout << i << " " << t[i].size() << "WTFWTF\n";
		for(int v, _v = 0; _v < t[i].size(); _v++) {
			v = t[i][_v];
			//cout << v << "Here" << endl;
			int j = i-1, f = 0, it = 0;
			while(j >= 0 && g[v].size() < 3) {
				for(int z = 1<<9; z>>=1;)
					if(f+z-1 < t[j].size() && add(seg(t[j],  f, f+z-1), {v})) f += z;
				if(f == t[j].size()) {
					//cout << "Bye\n";
					--j;
					++it;
					f = 0;
					continue;
				}
				
				g[v].push_back(t[j][f]);
				g[t[j][f]].push_back(v);
			
				//cout << v << " --- " << j << " / " << f << " " << t[j][f] << '\n';
			
				++f;
				if(i == 3) j--, f = 0;
				if(i == 2 && j && (it == 1 || !add(seg(t[j], f, (int)t[j].size()-1), {v}))) j--, f = 0;
				
				++it;
			}
		}
		//cout <<"Still not dead\n";
	}
	
	set<pair<int, int>> bad;
	for(int i = 1; i <= 2*n; i++) {
		if(g[i].size() == 1) continue;
		if(Query({g[i][0], g[i][1], i}) == 1) bad.insert(minmax(g[i][2], i));
		else if(Query({g[i][0], g[i][2], i}) == 1) bad.insert(minmax(g[i][1], i));
		else bad.insert(minmax(g[i][0], i));
	}
	for(int i = 1; i <= 2*n; i++) {
		while(bad.count(minmax(i, g[i].back()))) g[i].pop_back();
		if(i < g[i].back())
		Answer(i, g[i].back());
	}
}

Compilation message

chameleon.cpp: In function 'bool add(std::vector<int>, std::vector<int>)':
chameleon.cpp:11:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return x.size()<=500 && Query(x) == x.size();
                          ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:32:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int v, _v = 0; _v < t[i].size(); _v++) {
                      ~~~^~~~~~~~~~~~~
chameleon.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(f+z-1 < t[j].size() && add(seg(t[j],  f, f+z-1), {v})) f += z;
         ~~~~~~^~~~~~~~~~~~~
chameleon.cpp:39:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(f == t[j].size()) {
        ~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 25 ms 384 KB Output is correct
4 Correct 25 ms 384 KB Output is correct
5 Correct 33 ms 460 KB Output is correct
6 Correct 26 ms 512 KB Output is correct
7 Correct 25 ms 384 KB Output is correct
8 Correct 25 ms 384 KB Output is correct
9 Correct 26 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 4 ms 384 KB Wrong Answer [1]

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 4 ms 384 KB Wrong Answer [1]

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 39 ms 384 KB Output is correct
4 Correct 39 ms 384 KB Output is correct
5 Correct 43 ms 564 KB Output is correct
6 Correct 37 ms 384 KB Output is correct
7 Correct 36 ms 512 KB Output is correct
8 Correct 37 ms 448 KB Output is correct
9 Correct 36 ms 384 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 25 ms 384 KB Output is correct
4 Correct 25 ms 384 KB Output is correct
5 Correct 33 ms 460 KB Output is correct
6 Correct 26 ms 512 KB Output is correct
7 Correct 25 ms 384 KB Output is correct
8 Correct 25 ms 384 KB Output is correct
9 Correct 26 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Incorrect 4 ms 384 KB Wrong Answer [1]