Submission #1185604

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

messy

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <iomanip>
#include <queue>
#include <cassert>
#include <complex>
#include <cstring>
#include <memory>
#include <bitset>
#include <sstream>
#include <cmath>
#include <numeric>
#include <numbers>
#include <fstream>
#include "messy.h"

using namespace std;

#ifndef template
#ifndef define
 
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define pi pair<int, int>
#define nl cout << '\n';
#define x first
#define y second 
#define cbit(x) __builtin_popcountll(x)
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng) 
#define siz(x) (int)x.size()
 
#endif
 
#ifndef print
void print(size_t x) {cout << x << ' ';}
void print(int x) {cout << x << ' ';}
void print(long long x) {cout << x << ' ';}
void print(float x) {cout << x << ' ';}
void print(long double x) {cout << x << ' ';}
void print(char x) {cout << x << ' ';}
void print(const char* x) {cout << x << ' ';}
void print(bool x) {cout << x << ' ';}
void print(string &x) {cout << x << ' ';}
 
template<typename T, typename V>
void print(pair<T, V> &p) {print(p.x); print(p.y);}
template<typename T>
void print(vector<T> v) {for (int i = 0; i < v.size(); i++) print(v[i]);}
template<typename T>
void print(vector<vector<T>> v) {
    for (int i = 0; i < v.size(); i++){
        for (int j = 0; j < v[i].size(); j++)
            print(v[i][j]);
        nl;
    }
}
template <typename T, typename... V>
void print(T t, V&&... v) {print(t); print(v...);}
 
#endif
 
#ifndef read
void read(int &x) {cin >> x;}
void read(long long &x) {cin >> x;}
void read(unsigned &x) {cin >> x;}
void read(unsigned long long &x) {cin >> x;}
void read(float &x) {cin >> x;}
void read(long double &x) {cin >> x;}
void read(char &x) {cin >> x;}
void read(string &x) {cin >> x;}
void read(bool &x) {cin >> x;}
 
template<typename T> 
void read(vector<T> &v) {
    for (int i = 0; i < v.size(); i++)
        read(v[i]);
}
template <typename T, typename... V>
void read(T &t, V&... v) {read(t); read(v...);}
#endif
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template<class... Args>
auto vec(size_t n, Args&&... args) {
    if constexpr(sizeof...(args) == 1)
        return vector(n, args...);
    else
        return vector(n, vec(args...));
}

#endif

using namespace std;
const ll inf = 1e18;
const ll def = 1e5+1;
const ll mod = 1e9;

using namespace std;

// namespace helper {

//     set<string> set_;
//     bool compiled = false;
//     int n;
//     vector<int> p;
//     int w;
//     int r;

//     int read_int() {
//         int x;
//         cin >> x;
//         return x;
//     }

// }

// using namespace helper;


// // A convenience function.
// int get_p(int i) {
//     int ret = p[i];
//     return ret;
// }

// void wa() {
//     printf("WA\n");
//     exit(0);
// }

// bool check(const string& x) {
//     if ((int)x.length() != n) {
//         return false;
//     }
//     for (int i = 0; i < n; i++) {
//         if (x[i] != '0' && x[i] != '1') {
//             return false;
//         }
//     }
//     return true;
// }

// void add_element(string x) {
//     print("added", x); nl;
//     if (--w < 0 || compiled || !check(x)) {
//         wa();
//     }
//     set_.insert(x);
// }

// bool check_element(string x) {
//     print("checked", x, "-");
//     if (--r < 0 || !compiled || !check(x)) {
//         wa();
//     }
//     bool res = set_.count(x);
//     if (res)
//         print("yes");
//     else
//         print("no");
//     nl;
//     return res;
// }

// void compile_set() {
//     if (compiled) {
//         wa();
//     }
//     compiled = true;
//     set<string> compiledSet;
//     string compiledElement = string(n, ' ');
//     for (set<string>::iterator it = set_.begin(); it != set_.end(); it++) {
//         string s = *it;
//         for (int i = 0; i < n; i++) {
//             compiledElement[i] = s[get_p(i)];
//         }
//         compiledSet.insert(compiledElement);
//     }
//     set_ = compiledSet;
// }

vector<int> restore_permutation(int n, int w, int r){
    int k = 0, crr = 1;
    while (crr <= n){
        crr *= 2;
        k++;
    }
    string empty = "";
    for (int i = 0; i < n; i++) 
        empty += '0';
    for (int i = k - 1; i >= 1; i--){
        int len = 1 << i;
        for (int j = 0; j < n; j += len){
            int l = j, r = l + len - 1;
            string base = empty;
            for (int u = 0; u < n; u++){
                if (u >= l && u <= r)
                    continue;
                base[u] = '1';
            }
            for (int u = l; u <= (l + r) / 2; u++){
                string s = base;
                s[u] = '1';
                add_element(s);
            }
        }
    }
    compile_set();

    auto res = vec(n, make_pair(0, n - 1));
    for (int i = k - 1; i >= 1; i--){
        int len = 1 << i;
        for (int j = 0; j < n; j += len){
            int l = j, r = l + len - 1;
            string base = empty;

            int mid = (l + r) / 2;
            vector<int> left;
            
            for (int u = 0; u < n; u++){
                if (res[u] != make_pair(l, r))
                    base[u] = '1';
                else
                    left.push_back(u);
            }
            for (int u : left)
                res[u] = {mid + 1, r};
            for (int u : left){
                string s = base;
                s[u] = '1';
                if (check_element(s))
                    res[u] = {l, mid};
            }
        }
    }
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        p[i] = res[i].x;
    return p;
}    

/*
00000000
11110000
00001111

*/

// int32_t main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);

//     if (ifstream("input.txt").good()){
//         freopen("input.txt", "r", stdin);
//         freopen("output.txt", "w", stdout);
//     }

//     n = read_int();
//     w = read_int();
//     r = read_int();
//     p = vector<int>(n);
//     for (int i = 0; i < n; i++) {
//         p[i] = read_int();
//     }
//     vector<int> answer = restore_permutation(n, w, r);
    
//     if (answer.size() != n) {
//         printf("WA\n");
//         return 0;
//     }


//     printf("%d", answer[0]);

//     for (int i = 1; i < n; i++) {
//         printf(" %d", answer[i]);
//     }
//     printf("\n");
//     return 0;
// }

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