Submission #1324085

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

messy

#include <vector>
#include <string>
#include <algorithm>
#include "messy.h"

using namespace std;

/**
 * IOI 2016 - Unscrambling a Messy Bug
 * n = 128 uchun w = 896, r = 896 cheklovlariga mos yechim.
 */

void build(int n, int l, int r) {
    if (l + 1 == r) return;
    int mid = (l + r) / 2;
    
    // Chap bo'lakdagi bitlarni identifikatsiya qilish uchun maska qo'shamiz
    string s(n, '1');
    for (int i = l; i < r; i++) s[i] = '0';
    
    for (int i = l; i < mid; i++) {
        string t = s;
        t[i] = '1';
        add_element(t); // Chap bo'lakdagi har bir bit uchun bittadan son qo'shish [cite: 11, 50]
    }
    
    build(n, l, mid);
    build(n, mid, r);
}

vector<int> p;
vector<int> ans;

void solve(int n, int l, int r, vector<int> avail) {
    if (l + 1 == r) {
        ans[avail[0]] = l;
        return;
    }
    
    int mid = (l + r) / 2;
    string s(n, '1');
    for (int x : avail) s[x] = '0';
    
    vector<int> left_side, right_side;
    for (int x : avail) {
        string t = s;
        t[x] = '1';
        if (check_element(t)) { // Agar son to'plamda bo'lsa, u chap bo'lakka tegishli [cite: 57, 61]
            left_side.push_back(x);
        } else {
            right_side.push_back(x);
        }
    }
    
    solve(n, l, mid, left_side);
    solve(n, mid, r, right_side);
}

vector<int> restore_permutation(int n, int w, int r) {
    // 1. Yozish bosqichi
    build(n, 0, n);
    compile_set(); // Permutatsiyani ishga tushirish [cite: 13, 31, 54]
    
    // 2. O'qish va tiklash bosqichi
    ans.resize(n);
    vector<int> all_indices;
    for (int i = 0; i < n; i++) all_indices.push_back(i);
    
    solve(n, 0, n, all_indices);
    
    // Permutatsiya p[i] ni qaytarish (qaysi i bit p[i] ga o'tgan) [cite: 19, 44]
    vector<int> res(n);
    for (int i = 0; i < n; i++) res[i] = ans[i];
    return res;
}

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