Submission #59172

#	Time	Username	Problem	Language	Result	Execution time	Memory
59172		TadijaSebez	Unscrambling a Messy Bug (IOI16_messy)	C++11	100 / 100	4 ms	512 KiB

messy

#include "messy.h"
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <stdlib.h>
#include <ctime>
#include <algorithm>
using namespace std;
#define pb push_back
const int N=250;
int per[N];
vector<string> all;
map<string,bool> was;
int add,chk,m;
/*void add_element(string s){ all.pb(s);add++;}
void compile_set()
{
	int i,j;
	for(i=0;i<all.size();i++)
	{
		string tmp;
		for(j=0;j<m;j++) tmp+='0';
		for(j=0;j<m;j++) tmp[j]=all[i][per[j]];
		was[tmp]=1;
	}
}
bool check_element(string s){ chk++;return was[s];}*/
int n;
void Set(int l, int r)
{
	if(l==r) return;
	int mid=l+r>>1,i,j;
	string s;
	for(i=1;i<=n;i++) s+='1';
	for(i=l;i<=r;i++) s[i-1]='0';
	for(i=l;i<=mid;i++) s[i-1]='1',add_element(s),s[i-1]='0';
	Set(l,mid);Set(mid+1,r);
}
int sol[N];
void Solve(int l, int r, vector<int> v)
{
	if(l==r){ sol[v[0]]=l;return;}
	int mid=l+r>>1,i,j;
	string s;
	for(i=1;i<=n;i++) s+='1';
	for(i=0;i<v.size();i++) s[v[i]-1]='0';
	vector<int> ls,rs;
	for(i=0;i<v.size();i++)
	{
		s[v[i]-1]='1';
		if(check_element(s)) ls.pb(v[i]);
		else rs.pb(v[i]);
		s[v[i]-1]='0';
	}
	Solve(l,mid,ls);
	Solve(mid+1,r,rs);
}
vector<int> restore_permutation(int N, int w, int r)
{
	n=N;
	Set(1,n);
	compile_set();
	vector<int> v;
	int i;
	for(i=1;i<=n;i++) v.pb(i);
	Solve(1,n,v);
	vector<int> ans;
	for(i=1;i<=n;i++) ans.pb(sol[i]-1);
	return ans;
}
void test()
{
	int t,c=0,i,j;
	scanf("%i",&t);
	m=128;
	int lo=-1;
	int x=m;while(x) x>>=1,lo++;
	for(i=0;i<m;i++) per[i]=i;
	for(j=1;j<=t;j++)
	{
		random_shuffle(per,per+m);
		add=0;chk=0;
		was.clear();all.clear();
		vector<int> sol=restore_permutation(m,896,896);
		bool ok=1;
		for(i=0;i<m;i++) if(per[i]!=sol[i]) ok=0;
		if(!ok || add>m*lo || chk>m*lo)
		{
			printf("Test case %i:\n",j);
			printf("%i\n",m);
			for(i=0;i<m;i++) printf("%i ",per[i]);printf("\n");
			printf("My solution:\n");
			for(i=0;i<m;i++) printf("%i ",sol[i]);printf("\n");
			printf("Add: %i, Chk: %i\n",add,chk);
		}
		else c++;
	}
	printf("Add: %i, Chk: %i\n",add,chk);
	printf("%i of %i is correct!\n",c,t);
}
/*int main()
{
	srand(time(0));
	test();
	return 0;
	int i;
	scanf("%i",&m);
	for(i=0;i<m;i++) scanf("%i",&per[i]);
	vector<int> sol=restore_permutation(m,896,896);
	bool ok=1;
	for(i=0;i<m;i++) if(per[i]!=sol[i]) ok=0;
	for(i=0;i<m;i++) printf("%i ",sol[i]);printf("\n");
	if(ok) printf("OK\n");
	printf("Add: %i, Chk: %i\n",add,chk);
	return 0;
}*/

Compilation message (stderr)

messy.cpp: In function 'void Set(int, int)':
messy.cpp:33:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1,i,j;
          ~^~
messy.cpp:33:19: warning: unused variable 'j' [-Wunused-variable]
  int mid=l+r>>1,i,j;
                   ^
messy.cpp: In function 'void Solve(int, int, std::vector<int>)':
messy.cpp:44:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1,i,j;
          ~^~
messy.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v.size();i++) s[v[i]-1]='0';
          ~^~~~~~~~~
messy.cpp:49:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v.size();i++)
          ~^~~~~~~~~
messy.cpp:44:19: warning: unused variable 'j' [-Wunused-variable]
  int mid=l+r>>1,i,j;
                   ^
messy.cpp: In function 'void test()':
messy.cpp:92:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for(i=0;i<m;i++) printf("%i ",per[i]);printf("\n");
    ^~~
messy.cpp:92:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for(i=0;i<m;i++) printf("%i ",per[i]);printf("\n");
                                          ^~~~~~
messy.cpp:94:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for(i=0;i<m;i++) printf("%i ",sol[i]);printf("\n");
    ^~~
messy.cpp:94:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for(i=0;i<m;i++) printf("%i ",sol[i]);printf("\n");
                                          ^~~~~~
messy.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&t);
  ~~~~~^~~~~~~~~

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