Submission #1216512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216512		CELD_07	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	1 ms	584 KiB

messy

#include "messy.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}

string v5;
inline void r2(ll tl, ll tr){
if(tl==tr){
add_element(v5);
return;
}
ll tm=(tl+tr)/2;
for(int i=tl; i<=tr; i++)v5[i]='0';
for(int i=tl; i<=tm; i++){v5[i]='1';add_element(v5);v5[i]='0';}
for(int i=tl; i<=tr; i++)v5[i]='1';
r2(tl, tm);
r2(tm+1, tr);
}
vector<int> res;
vector<vector<ll>> t;
inline void r1(ll v, ll tl, ll tr){
if(tl==tr){
res[tl]=t[v][0];
return;
}
ll tm=(tl+tr)/2;
for(auto y: t[v])v5[y]='0';
for(auto y: t[v]){
v5[y]='1';
bool o=check_element(v5);
if(o)t[v*2].push_back(y);
else t[v*2+1].push_back(y);
v5[y]='0';
}
for(auto y: t[v])v5[y]='1';
r1(v*2, tl, tm);
r1(v*2+1, tm+1, tr);
}

vector<int> restore_permutation(int n, int w, int r){
vector<vector<ll>>().swap(t);
t.resize(4*n);
vector<tuple<ll, ll, ll>> ind, ind1;
for(int i=0; i<n; i++)t[1].push_back(i);
v5="";
for(int i=0; i<n; i++)v5+='1';
vector<int>().swap(res);
res.assign(n, 0);
r2(0, n-1);
compile_set();
r1(1, 0, n-1);
vector<int>res1;
vector<int>().swap(res1);
res1.assign(n, -1);
for(int i=0; i<n; i++)res1[res[i]]=i;
return res1;
}

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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