oj.uz

Submission #423850

# Submission time Handle Problem Language Result Execution time Memory
423850 2021-06-11T13:16:56 Z oolimry Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 67 ms 424 KB 
#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;

vector<int> adj[1005];
int likes[1005];
int answered[1005];

void addedge(int u, int v){
	//show2(u,v);
	adj[u].push_back(v);
	adj[v].push_back(u);
}

void answer(int u, int v){
	//show3("ANS", u, v);
	if(answered[u] or answered[v]) return;
	answered[u] = 1;
	answered[v] = 1;
	Answer(u,v);
}

///claim: if A is an independent set, then A+v is independent iff query(A) < query(A+v)

vector<int> stuff[4];

vector<int> copy(vector<int> b){
	vector<int> res(sz(b));
	for(int i = 0;i < sz(b);i++) res[i] = b[i];
	return res;
}

inline bool independent(vector<int> v, int u){
	v.push_back(u);
	return (sz(v)-1 < Query(v));
}

void Solve(int n){
	srand(12323);
	vector<int> order;
	for(int i = 1;i <= 2*n;i++) order.push_back(i);
	random_shuffle(all(order));
	
	for(int u : order){
		int insertplace = -1;
		int found = 0;
		for(int j = 0;j < 4;j++){
			if(stuff[j].empty()){
				if(insertplace == -1) insertplace = j;
				continue;
			}
			
			vector<int> v = copy(stuff[j]);
			
			if(found == 3 or independent(v, u)){ ///is independent set
				if(insertplace == -1) insertplace = j;
				continue;
			}
						
			while(true){
				if(v.empty()) break;
				if(independent(v, u)) break;
				
				int low = -1, high = sz(v)-1;
				
				while(low != high-1){
					int mid = (low+high)/2;
					vector<int> nv;
					for(int i = 0;i <= mid;i++) nv.push_back(v[i]);
					
					if(independent(nv, u)) low = mid;
					else high = mid;
				}
				
				found++;
				addedge(u, v[high]);
				vector<int> ov;
				for(int i = high+1;i < sz(v);i++) ov.push_back(v[i]);
				swap(v,ov);
				ov.clear();
			}
		}
		
		//show2(u, insertplace);
		stuff[insertplace].push_back(u);
	}
		
	///the last stuff;
	for(int i = 1;i <= 2*n;i++){
		//if(answered[i]) continue;
		if(sz(adj[i]) == 1){
			answer(i, adj[i][0]);
			//show2(i, adj[i][0]);
		}
		else if(sz(adj[i]) == 3){
			vector<int> &v = adj[i];
			if(Query({i,v[0],v[1]}) == 1) likes[i] = v[2];
			if(Query({i,v[2],v[1]}) == 1) likes[i] = v[0];
			if(Query({i,v[0],v[2]}) == 1) likes[i] = v[1];
			//show2(i, likes[i]);
		}
		else assert(false);
	}
	
	for(int i = 1;i <= 2*n;i++){
		if(answered[i]) continue;
		for(int x : adj[i]){
			if(likes[x] != i and likes[i] != x) answer(i,x);
		}
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 38 ms 412 KB Output is correct
4 Correct 41 ms 424 KB Output is correct
5 Correct 46 ms 420 KB Output is correct
6 Correct 39 ms 424 KB Output is correct
7 Correct 39 ms 328 KB Output is correct
8 Correct 38 ms 328 KB Output is correct
9 Correct 38 ms 424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 328 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 67 ms 328 KB Output is correct
4 Incorrect 67 ms 328 KB Wrong Answer [3]
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 38 ms 412 KB Output is correct
4 Correct 41 ms 424 KB Output is correct
5 Correct 46 ms 420 KB Output is correct
6 Correct 39 ms 424 KB Output is correct
7 Correct 39 ms 328 KB Output is correct
8 Correct 38 ms 328 KB Output is correct
9 Correct 38 ms 424 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 0 ms 328 KB Output is correct
12 Correct 0 ms 328 KB Output is correct
13 Correct 0 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 0 ms 328 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 1 ms 328 KB Output is correct
23 Correct 1 ms 328 KB Output is correct
24 Correct 1 ms 328 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1 ms 328 KB Output is correct
28 Correct 1 ms 328 KB Output is correct
29 Correct 0 ms 328 KB Output is correct
30 Correct 67 ms 328 KB Output is correct
31 Incorrect 67 ms 328 KB Wrong Answer [3]
32 Halted 0 ms 0 KB -