Submission #339680

#	Time	Username	Problem	Language	Result	Execution time	Memory
339680		ogibogi2004	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	2 ms	492 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int pos[128];
void add(int l,int r,int n)
{
	if(l==r)return;
	string s="";
	for(int i=0;i<n;i++)
	{
		if(i<l||i>r)s+="1";
		else s+="0";
	}
	for(int i=l;i<=(l+r)/2;i++)
	{
		s[i]='1';
		add_element(s);
		s[i]='0';
	}
	add(l,(l+r)/2,n);
	add((l+r)/2+1,r,n);
}
void solve(int l,int r,int n,vector<int>v)
{
	if(l==r)
	{
		if(v.size()==0)cout<<"xd\n";
		pos[v[0]]=l;
		return;
	}
	string s="";
	for(int i=0;i<n;i++)
	{
		bool inv=0;
		for(int j=0;j<v.size();j++)
		{
			if(v[j]==i){inv=1;break;}
		}
		if(inv)s+="0";
		else s+="1";
	}
	vector<int>lh,rh;
	for(int i=0;i<v.size();i++)
	{
		s[v[i]]='1';
		if(check_element(s))
		{
			lh.push_back(v[i]);
		}
		else rh.push_back(v[i]);
		s[v[i]]='0';
	}
	int mid=(l+r)/2;
	solve(l,mid,n,lh);
	solve(mid+1,r,n,rh);
}
vector<int> restore_permutation(int n, int w, int r) {
    /*add_element("0");
    compile_set();
    check_element("0");
    return std::vector<int>();*/
   // cout<<"*\n";
    add(0,n-1,n);
   // cout<<"*\n";
    compile_set();
   // cout<<"*\n";
    vector<int>v;
    for(int i=0;i<n;i++)v.push_back(i);
    memset(pos,-1,sizeof(pos));
    solve(0,n-1,n,v);
   // cout<<"*\n";
    vector<int>ret;
    for(int i=0;i<n;i++)
    {
		ret.push_back(pos[i]);
		continue;
		for(int j=0;j<n;j++)
		{
			if(pos[j]==i){ret.push_back(j);break;}
		}
	}
	return ret;
}

Compilation message (stderr)

messy.cpp: In function 'void solve(int, int, int, std::vector<int>)':
messy.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int j=0;j<v.size();j++)
      |               ~^~~~~~~~~
messy.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0;i<v.size();i++)
      |              ~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30