Submission #1153572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153572		zhasyn	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	2 ms	1844 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 128 + 100, M = 1e7 + 10, len = 21, inf = 1e18;
const ll mod = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
int n, cnt, pos[N], per[N];
string orig = "";
void calc(int l, int r){
	//cout << l << " "<< r << endl;
	if(r - l == 1) return;
	int mid = (l + r) / 2;
	calc(l, mid);
	calc(mid, r);
	string s = orig;
	for(ll i = 0; i < l; i++){
		s[i] = '1';
	}
	for(ll i = r; i < n; i++){
		s[i] = '1';
	}
	for(ll i = l; i < mid; i++){
		s[i] = '1';
		add_element(s);
		s[i] = '0';
	}
}
vector <int> over;
vector <int> nums[N][N];
bool need[N];
string nw;
void gt(int from, int to, int l = 0, int r = n){
	if(from <= l && r <= to) return;
	int mid = (r + l) / 2;
	if(to <= mid){
		for(auto u : nums[mid][r]){
			nw[u] = '1';
		}
		gt(from, to, l, mid);
	} else{
		for(auto u : nums[l][mid]){
			nw[u] = '1';
		}
		gt(from, to, mid, r);
	}
}
vector<int> restore_permutation(int nx, int w, int r){
	n = nx;
	for(int i = 0; i < n; i++){
		orig += '0';
	}
	calc(0, n);
	for(int i = 0; i < n; i++){
		nums[0][n].pb(i);
	}
    compile_set();
    vector <int> vec;
    for(int len = n; len >= 2; len /= 2){
    	for(int i = 0; i < n; i += len){
    		nw = orig;
    		gt(i, i + len);
    		//cout << nw << " nw\n";
    		int mid = i + len/2;
    		for(auto u : nums[i][i + len]){
    			need[u] = true;
    			//cout << u << " upd\n";
    		}
    		for(auto u : nums[i][i + len]){
    			nw[u] = '1';
    			bool rs = check_element(nw);
    			if(rs){
	    			for(int k = 0; k < (int)nw.size(); k++){
	    				if(nw[k] == '1' && need[k]){
	    					nums[i][mid].pb(k);
	    					need[k] = false;
	    				}
	    			}
    			}
    			nw[u] = '0';
    		}
    		for(auto u : nums[i][i + len]){
    			if(need[u]) nums[mid][i + len].pb(u);
    			need[u] = false;
    		}
    	}
    }
    for(int i = 0; i < n; i++){
    	pos[nums[i][i + 1][0]] = i;
    }
    for(int i = 0; i < n; i++){
    	vec.pb(pos[i]);
    }
    return vec;
}

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