oj.uz

Submission #1049910

# Submission time Handle Problem Language Result Execution time Memory
1049910 2024-08-09T06:03:51 Z 김은성(#11046) Chameleon's Love (JOI20_chameleon) C++17
4 / 100
 9 ms 460 KB 
#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int cnt = 0;
int askrange(vector<int> cur, int i, int j){
	vector<int> temp;
	for(int u: cur)
		temp.push_back(u);
	for(int k=i; k<=j; k++)
		temp.push_back(vec[k]);
	cnt++;
	assert(cnt <= 20000);
	return Query(temp);
}
int askrange2(vector<int> cur, int i, int j, int i2, int j2){
	vector<int> temp;
	for(int u: cur)
		temp.push_back(u);
	for(int k=i; k<=j; k++)
		temp.push_back(vec[k]);
	for(int k=i2; k<=j2; k++)
		temp.push_back(vec[k]);
	cnt++;
	assert(cnt <= 20000);
	return Query(temp);
}
void Solve(int N) {
	int i;
	for(i=1; i<=2*N; i++)
		vec.push_back(i);
	for(i=1; i<=N; i++){
		int lo = 0, hi = (int)vec.size() - 1, mid;
		while(1){
			mid = (lo+hi) / 2;
			if(askrange({}, lo, mid) < mid-lo+1)
				hi = mid;
			else if(askrange({}, mid+1, hi) < hi-mid)
				lo = mid+1;
			else
				break;
		}
		int lo1 = lo, hi1 = mid, lo2 = mid+1, hi2 = hi;
		while(lo1 < hi1 || lo2 < hi2){
		//printf("lo1=%d lo2=%d\n", lo1, lo2);
			int mid1 = (lo1+hi1)/2, mid2 = (lo2+hi2)/2;
			if(askrange2({}, lo1, mid1, lo2, mid2) < mid1-lo1+1 + mid2-lo2+1){
				hi1 = mid1;
				hi2 = mid2;
			}
			else if(askrange2({}, lo1, mid1, mid2+1, hi2) < mid1-lo1+1 + hi2-mid2){
				hi1 = mid1;
				lo2 = mid2+1;
			}
			else if(askrange2({}, mid1+1, hi1, lo2, mid2) < hi1-mid1 + mid2-lo2+1){
				lo1 = mid1+1;
				hi2 = mid2;
			}
			else{
				lo1 = mid1+1;
				lo2 = mid2+1;
			}
		}
		//printf("vec[lo1]=%d vec[lo2]=%d lo1=%d lo2=%d\n", vec[lo1], vec[lo2], lo1, lo2);
		int a = vec[lo1], b = vec[lo2];
		Answer(vec[lo2], vec[lo1]);
		vec.erase(find(vec.begin(), vec.end(), a));
		vec.erase(find(vec.begin(), vec.end(), b));
		//for(int u: vec)
		//	printf("%d ", u);
		//printf("\n");
	}
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 8 ms 460 KB Output is correct
5 Correct 8 ms 460 KB Output is correct
6 Correct 9 ms 460 KB Output is correct
7 Correct 8 ms 344 KB Output is correct
8 Correct 9 ms 344 KB Output is correct
9 Correct 9 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 ms 344 KB Wrong Answer [6]
12 Halted 0 ms 0 KB -