Submission #362441

#	Time	Username	Problem	Language	Result	Execution time	Memory
362441		David_M	Unscrambling a Messy Bug (IOI16_messy)	C++14	0 / 100	373 ms	524292 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
#define pb push_back
using namespace std;

string s;
vector<int> Ans(128);
int A[128*14];
vector <int> v, V;
int sz[7], f[128];
bool g[7][7];

void buildA(int x=1, int l=0, int r=128, int y=0){
	if(y==7)return;
	for (int i=max(l, 7); i<r; i++)
		A[x]+=(!(i&(1<<(6-x))));
	buildA(x+1, l, l+r>>1, y+1);
	buildA(x+1, l+r>>1, r);
}
void add(int x,int y=-1){  s[x]='1';if(y>=0)s[y]='1';     add_element(s);    s[x]='0';if(y>=0)s[y]='0';}
bool check(int x,int y=-1){s[x]='1';if(y>=0)s[y]='1';return check_element(s);s[x]='0';if(y>=0)s[y]='0';}

void ADD(){
	for (int i=0; i<7; i++)add(i);
	for (int i=0; i<6; i++)add(i, i+1);
    add(1, 4);

    for (int i=0; i<7; i++)
    	for (int j=7; j<128; j++)
    		if(!(j&(1<<(6-i))))add(i, j);
}
void find7(){
    
    for (int i=0; i<128; i++)
    	if(check(i))v.pb(i),f[i]=1;
	
	for (int i=0; i<6; i++)
		for (int j=i+1; j<7; j++){
			g[i][j]=g[j][i]=check(v[i], v[j]);
			sz[i]+=g[i][j];
			sz[j]+=g[i][j];
	}
	
	for (int i=0; i<7; i++){
		if(sz[i]>1)continue;
		for (int j=0; j<7; j++){
			if(!g[i][j] || sz[j]!=3)continue;
			
			for (int k=0; k<7; k++)
				if(g[j][k] && sz[k]==3)g[j][k]=g[k][j]=0;
			
			V.pb(v[i]);
			int x=i, pa=i, o=0;
			while(!o){ o=1;
				for (int k=0; k<7; k++)
					if(g[x][k] && k!=pa)
						V.pb(v[k]), o=0, pa=x, x=k;
			}
		}
	}	
	for (int i=0; i<7; i++)Ans[V[i]]=i;
}
void solve(vector<int> p, int e=0, int x=1){
	if(e==7 || p.size()==0)return;
	
	int n=p.size(), T=(1<<(6-e)), k=0;
	
	vector<int> L, R;
	for (int i=0; i<n-1; i++)
		if(check(V[e], p[i])) L.pb(p[i]), k++;
		else Ans[p[i]]+=T,    R.pb(p[i]);
	
	if (k<A[x]) L.pb(p[n-1]);
	else Ans[p[n-1]]+=T, R.pb(p[n-1]);
	
	solve(L, e+1, x<<1);
	solve(R, e+1, x<<1|1);
}
void findall(){	
	vector <int> p;
	for (int i=0; i<128; i++)if(!f[i])p.pb(i);
	solve(p);
}

vector<int> restore_permutation(int n, int w, int r){
    
    for (int i=0; i<128; i++)s+='0';
    buildA();
	ADD();
	compile_set();
	find7();
	findall();
    return Ans;
}

Compilation message (stderr)

messy.cpp: In function 'void buildA(int, int, int, int)':
messy.cpp:17:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |  buildA(x+1, l, l+r>>1, y+1);
      |                 ~^~
messy.cpp:18:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  buildA(x+1, l+r>>1, r);
      |              ~^~
messy.cpp: In function 'void find7()':
messy.cpp:34:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   34 |     for (int i=0; i<128; i++)
      |     ^~~
messy.cpp:37:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   37 |  for (int i=0; i<6; i++)
      |  ^~~

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