Submission #758926

#	Time	Username	Problem	Language	Result	Execution time	Memory
758926		minhcool	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	468 KiB

messy

//#define local
#ifndef local
#include "messy.h"
#endif
 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int n;
 
bool in[N];
 
void run(){
    string s;
    for(int i = 0; i < n; i++) s += char(48 + in[i]);
    add_element(s);
}
 
void gen(int l, int r){
    if(l >= r) return;
    int mid = (l + r) >> 1;
    for(int i = 0; i < n; i++) in[i] = 1;
    for(int i = l; i <= r; i++) in[i] = 0;
    for(int i = mid + 1; i <= r; i++){
        in[i] = 1;
        run();
        in[i] = 0;
    }
    gen(l, mid);
    gen(mid + 1, r);
}
 
bool get(){
    string s;
    for(int i = 0; i < n; i++) s += char(48 + in[i]);
    return check_element(s);
}
 
vector<int> ans;
 
void ask(int l, int r, vector<int> v){
//	cout << l << " " << r << " " << v.size() << " ";
//	for(auto it : v) cout << it << " ";
//	cout << "\n";
    if(l == r){
        ans[v[0]] = l;
        return;
    }
    int mid = (l + r) >> 1;
    for(int i = 0; i < n; i++) in[i] = 1;
    for(auto it : v) in[it] = 0;
    vector<int> v1, v2;
    for(auto it : v){
        in[it] = 1;
        if(get()) v2.pb(it);
        else v1.pb(it);
        in[it] = 0;
    }
   // int mid = (l + r) >> 1;
    ask(l, mid, v1);
    ask(mid + 1, r, v2);
}
 
 
vector<int> restore_permutation(int N, int w, int r) {
    n = N;
    ans.resize(n);
    gen(0, n - 1);
    compile_set();
    vector<int> inds;
    for(int i = 0; i < n; i++) inds.pb(i);
    ask(0, n - 1, inds);
    return ans;
}
 
 
//#define local
#ifdef local
void process(){
 
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Compilation message (stderr)

messy.cpp:23:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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