Submission #750984

#	Time	Username	Problem	Language	Result	Execution time	Memory
750984		puppy	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	472 KiB

messy

#include <vector>
#include <iostream>
#include "messy.h"
using namespace std;
int calc(int i, int j)
{
    //i를 j번 비트까지 봤을 때
    int ans = 0;
    for (int k = 6; k >= j; k--) ans += i & 1 << k;
    return ans;
}
std::vector<int> restore_permutation(int n, int w, int r) {
    string s(n, '0');
    for (int i = 0; i <= 6; i++) {
        s[i] = '1';
        add_element(s);
        s[i] = '0';
    }
    for (int i = 1; i < n; i++) s[i] = '1';
    add_element(s);
    for (int i = 1; i < n; i++) s[i] = '0';
    s[0] = '1';
    for (int i = 1; i <= 5; i++) {
        s[i] = '1';
        add_element(s);
    }
    for (int i = 0; i <= 6; i++) s[i] = '0';
    for (int i = 7; i < n; i++) {
        for (int j = 0; j < 7; j++) {
            if (i & (1 << j)) {
                s[i] = '1';
                s[j] = '1';
                add_element(s);
                s[i] = '0';
                s[j] = '0';
            }
        }
    }
    compile_set();
    vector<int> p(n, -1);
    vector<int> lst;
    //일단 처음에 1인 애들을 다 찾으면 얘녜 p[i] = 0, 1, ..., 6임
    for (int i = 0; i < n; i++) {
        s[i] = '1';
        if (check_element(s)) {
            lst.push_back(i);
        }
        s[i] = '0';
    }
    vector<int> rev(n);
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < n; j++) {
            if (lst[i] != j) s[j] = '1';
        }
        if (check_element(s)) {
            rev[0] = lst[i];
            p[lst[i]] = 0;
        }
        for (int j = 0; j < n; j++) s[j] = '0';
    }
    s[rev[0]] = '1';
    for (int i = 1; i <= 5; i++) {
        //i번째 거 알아내기: 지금까지
        for (int j = 0; j < 7; j++) {
            if (p[lst[j]] != -1) continue;
            //j인지 테스트
            s[lst[j]] = '1';
            if (check_element(s)) {
                rev[i] = lst[j];
                p[lst[j]] = i;
            }
            s[lst[j]] = '0';
        }
        s[rev[i]] = '1';
    }
    for (int j = 0; j < 7; j++) {
        if (p[lst[j]] == -1) {
            p[lst[j]] = 6;
            rev[6] = lst[j];
        }
    }
    for (int i = 0; i < n; i++) s[i] = '0';
    //이제 0부터 6번까지를 다 구함
    vector<vector<int>> cnt(7, vector<int>(128));
    //i가 등장했는가 여부: rev[i] 체크
    //cnt[i][j]: i번 비트까지 봤을 때 j인 것이 몇 개인가
    //ouc[i][j]: i번 비트까지 봤을 때 j인 것이 몇 개 나왔는가, 로 갈게요
    for (int i = 7; i < n; i++) {
        for (int k = 6; k >= 0; k--) cnt[k][calc(i, k)]++;
    }
    for (int i = 0; i < n; i++) {
        if (p[i] != -1) continue;
        int ret = 0;
        for (int k = 6; k >= 0; k--) {
            if (cnt[k][ret+(1<<k)] == 0) {
                //비트 1 확정
                cnt[k][ret]--;
            }
            else if (cnt[k][ret] == 0) {
                ret += (1<<k);
                cnt[k][ret]--;
            }
            else {
                s[i] = '1';
                s[rev[k]] = '1';
                if (check_element(s)) {
                    ret += (1<<k);
                    cnt[k][ret]--;
                }
                else {
                    cnt[k][ret]--;
                }
                s[i] = '0';
                s[rev[k]] = '0';
            }
            //k번째 비트까지 봤을 때 ret + (1 << k)인 것의 개수가 0개 남았거나
            //k번째 비트까지 봤을 때 ret인 것의 개수가 0개 남았는지 체크
        }
        //i번의 원래 번호가 ret였다
        rev[ret] = i;
        p[i] = ret;
    }
    return p;
}

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