Submission #362475

#	Time	Username	Problem	Language	Result	Execution time	Memory
362475		David_M	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	512 KiB

messy

//write: 7 + 6 + 408 = 421
//read: 128 + 21 + 724 = 873
//maximum 2 '1'-s per query
#include <bits/stdc++.h>
#include "messy.h"
#define pb push_back
using namespace std;
 
string s;
vector<int> Ans(128);
int A[128*4], N=128, lg=7, LG=7;
vector <int> v, V;
int sz[7], f[128];
bool g[7][7];
 
void buildA(int x=1, int l=0, int r=N, int y=0){
	if(y==lg)return;
	for (int i=max(l, LG); i<r; i++)
		A[x]+=(!(i&(1<<(lg-1-y))));
	buildA(x<<1, l, l+r>>1, y+1);
	buildA(x<<1|1, l+r>>1, r, y+1);
}
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';bool b=check_element(s);s[x]='0';if(y>=0)s[y]='0';return b;}
 
void ADD(){
	for (int i=0; i<LG; i++)add(i);
	for (int i=0; i<LG-1; i++)add(i, i+1);
    add(1, LG-3);
 
    for (int i=0; i<lg; i++)
    	for (int j=LG; j<N; j++)
    		if(!(j&(1<<(lg-1-i))))add(i, j);
}
void findlg(){
    
    for (int i=0; i<N; i++)
    	if(check(i))v.pb(i),f[i]=1;
	
	for (int i=0; i<LG-1; i++)
		for (int j=i+1; j<LG; 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<LG; i++){
		if(sz[i]>1)continue;
		for (int j=0; j<LG; j++){
			if(!g[i][j] || sz[j]!=3)continue;
			
			for (int k=0; k<LG; 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<LG; k++)
					if(g[x][k] && k!=pa)
						V.pb(v[k]), o=0, pa=x, x=k;
			}
		}
	}	
	for (int i=0; i<LG; i++)Ans[V[i]]=i;
}
void solve(vector<int> p, int e=0, int x=1){
	if(e==lg || p.size()==0)return;
	
	int n=p.size(), T=(1<<(lg-1-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<N; i++)if(!f[i])p.pb(i);
	solve(p);
}
 
vector<int> restore_permutation(int n, int w=0, int r=0){
    if(n==32)N=32, lg=5, Ans.resize(32);
    if(n==8)N=8, lg=3, Ans.resize(8);
    for (int i=0; i<N; i++)s+='0';
    buildA();
	ADD();
	compile_set();
	findlg();
	findall();
    return Ans;
}

Compilation message (stderr)

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

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