Submission #623115

#	Time	Username	Problem	Language	Result	Execution time	Memory
623115		l_reho	Combo (IOI18_combo)	C++14	10 / 100	57 ms	488 KiB

combo

#include "combo.h"

#include<bits/stdc++.h>
using namespace std;

int press(std::string p);

std::string guess_sequence(int N) {
  
	// guess del primo carattere
	string guess = "A";
	vector<string> voc{"A", "B", "X", "Y"};

	for(int i = 0; i < 4; i++){
		int ret = press(voc[i]);
		if(ret == 1){
			guess = voc[i];
			break;
		}
	}
	
	voc.erase(find(voc.begin(), voc.end(), guess));
	
	
	for(int i = 1; i < N; i++){
		
		int low = 0;
		int high = 3;
		string v = "";
		while(low <= high){
			int mid = low + (high-low)/2;
			
			string left = "";
			for(int j = low; j <= mid; j++)
				left += guess + voc[j];
			
			if(press(left) == (int)guess.length()+1){
				v = voc[mid];
				
				high = mid-1;
			}else{
				low = mid+1;
			}
			
		}
		
		guess += v;
		
		/*
		for(int j = 0; j < 4; j++){
			if(voc[j][0] == guess[0]) continue;
			int ret = press(guess + voc[j]);	
			
			if(ret == (int)guess.length()+1){
				guess += voc[j];
				break;
			}
			
		}
		*/
		
	}
	
	return guess;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 95