Submission #311750

#	Time	Username	Problem	Language	Result	Execution time	Memory
311750		zakaF	Combo (IOI18_combo)	C++14	30 / 100	55 ms	844 KiB

combo

    #include <iostream>
    #include <cstdlib>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <set>
    #include <map>
    #include <unordered_set>
    #include <unordered_map>
    #include <cstring>
    #include "combo.h"
    using namespace std;
    using ll = long long;
    using ld = long double;
    using uint = unsigned int;
    using ull = unsigned long long;
     
    #define pb push_back
    #define mp make_pair
    #define sz(x) (int)x.size()
    #define all(x) (x).begin(),(x).end()
    #define rall(x) (x).rbegin(),(x).rend()
    #define fi first
    #define se second
    #ifdef LOCAL
    	#include </home/linux/debug.h>
    	#define dbg(...) cout << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", _print(__VA_ARGS__)
    #else
    	#define dbg(...)
    #endif
string guess_sequence(int N)
{
    		string ans;
    		vector<string> a[N+1];
    		if(press("A") == 1)
    			ans = "A";
    		else if(press("B")==1)
    			ans = "B";
    		else if(press("X") == 1)
    			ans = "X";
    		else
    			ans = "Y";
    		a[0] = {"A","B","X","Y"};
    		for(int i = 1;i<N;i++)
    		{
    			for(string x:a[0])
    				if(x!=ans)
    					a[i].pb(x);
    		}
     
    		for(int i = 1;i<N-1;i++)
    		{
    			if(sz(a[i]) == 1)
    			{
    				ans+=a[i][0];
    				continue;
    			}
    			bool did = 0;
    			for(int j = 0;j<sz(a[i])-1&&!did;j++)
    			{
    				
    				for(int k = 0;k<sz(a[i+1])&&!did;k++)
    				{
    					int x = press(ans+a[i][j]+a[i+1][k]);
    					if(x == i+2)
    					{
    						ans+=a[i][j]+a[i+1][k];
    						did = 1;
    						i++;
    					}
    					else if(x == i+1)
    					{
    						ans+=a[i][j];
    						a[i+1].erase(a[i+1].begin()+k);
    						did = 1;
    					}
    					else
    						break;
    				}
    			}
    			if(!did)
    				ans+=a[i].back();
    		}
    		if(sz(ans) == N)
    			return ans;
    		if(sz(a[N-1]) == 1)
    				ans+=a[N-1][0];
    			else
    			{
    				for(int i = 0;i<sz(a[N-1])-1;i++)
    					if(press(ans+a[N-1][i])==N)
    					{
    						ans+=a[N-1][i];
    						break;
    					}
    				if(sz(ans)<N)
    					ans+=a[N-1].back();
    			}
    	return ans;
}

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