Submission #102062

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

messy

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#include "messy.h"

string t;
vector<int> ans;

void add(int l,int r)
{
	if(l==r) return; 
	int m=l+r>>1;
	for(int i=l;i<=m;++i)
		t[i]='1',add_element(t),t[i]='0';
	for(int i=m+1;i<=r;++i)
		t[i]='1';
	add(l,m);
	for(int i=m+1;i<=r;++i)
		t[i]='0';
	for(int i=l;i<=m;++i)
		t[i]='1';
	add(m+1,r);
	for(int i=l;i<=m;++i)
		t[i]='0';
}

void query(int l,int r,vector<int> &v)
{
	if(l==r) return ans[v[0]]=l,void();
	vector<int> L,R;
	for(int i=0;i<v.size();++i)
	{
		t[v[i]]='1';
		if(check_element(t)) L.pb(v[i]);
		else R.pb(v[i]);
		t[v[i]]='0';
	}
	int m=l+r>>1;
	for(int i:R)
		t[i]='1';
	query(l,m,L);
	for(int i:R)
		t[i]='0';
	for(int i:L)
		t[i]='1';
	query(m+1,r,R);
	for(int i:L)
		t[i]='0';
}

vector<int> restore_permutation(int n, int w, int r) 
{
	vector<int> ls;
	ans.resize(n),t.resize(n,'0');
	for(int i=0;i<n;++i)
		ls.pb(i);
    add(0,n-1);
    compile_set();
    query(0,n-1,ls);
    return ans;
}

Compilation message (stderr)

messy.cpp: In function 'void add(int, int)':
messy.cpp:25:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
messy.cpp: In function 'void query(int, int, std::vector<int>&)':
messy.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();++i)
              ~^~~~~~~~~
messy.cpp:51:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

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