제출 #1368574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368574		bronze_coder	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	1 ms	580 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;


vector<int> restore_permutation(int n,int w,int r){
    string s(n,'0');
    for(int i=0;i<n;i++){
        int x = 1;
        while(x<n){
            if(i&x){
                s[x] = '1';
                s[i] = '1';
                add_element(s);
                s[x] = '0';
                s[i] = '0';
            }
            x *= 2;
        }
    }
    vector<int> a = {1};
    while(a[a.size()-1]*2<n){
        a.push_back(a[a.size()-1]*2);
    }
    for(int i=0;i<a.size();i++){
        for(int j=0;j<=i;j++){
            if(i+j<a.size()){
                if(i==j){
                    for(int k=0;k<n;k++){
                        if(k!=a[i]){
                            s[k] = '1';
                        }
                    }
                    add_element(s);
                    for(int k=0;k<n;k++){
                        s[k] = '0';
                    }
                    continue;
                }
                s[a[i]] = '1';
                s[a[j]] = '1';
                add_element(s);
                s[a[i]] = '0';
                s[a[j]] = '0';
            }
        }
    }
    compile_set();
    string s1(n,'0');
    vector<int> ans(n,-1);
    vector<int> l;
    vector<int> c(n,0);
    for(int i=0;i<n;i++){
        s1[i] = '1';
        if(check_element(s1)){
            l.push_back(i);
            c[i] = 1;
        }
        s1[i] = '0';
    }
    map<pair<int,int>,int> m;
    for(int i:l){
        for(int j:l){
            if(j<i){
                s1[i] = '1';
                s1[j] = '1';
                if(check_element(s1)){
                    m[{i,j}] = 1;
                    m[{j,i}] = 1;
                }
                s1[i] = '0';
                s1[j] = '0';
            }
        }
    }
    for(int i:l){
        int z = 0;
        for(int j:l){
            if(i!=j){
                if(m[{i,j}]){
                    z++;
                }
            }
        }
        for(int j=0;j<n;j++){
            if(j!=i){
                s1[j] = '1';
            }
        }
        if(check_element(s1)){
            z += 1;
        }
        for(int j=0;j<n;j++){
            s1[j] = '0';
        }
        ans[i] = 1<<a.size()-z;
    }
    set<int> s2;
    for(int i=0;i<n;i++){
        s2.insert(i);
    }
    for(int i=1;i<n;i*=2){
        s2.erase(i);
    }
    for(int i=0;i<n;i++){
        vector<int> l1;
        for(int j:s2){
            l1.push_back(j);
        }
        if(ans[i]==-1){
            ans[i] = 0;
            for(int j:l){
                vector<int> l2;
                vector<int> l3;
                for(int k:l1){
                    if(k&ans[j]){
                        l2.push_back(k);
                    }
                    else{
                        l3.push_back(k);
                    }
                }
                if(l2.size()>0&&l3.size()>0){
                    s1[i] = '1';
                    s1[j] = '1';
                    if(check_element(s1)){
                        ans[i] ^= ans[j];
                        l1 = l2;
                    }
                    else{
                        l1 = l3;
                    }
                    s1[i] = '0';
                    s1[j] = '0';
                }
                else{
                    if(l2.size()>0){
                        l1 = l2;
                        ans[i] ^= ans[j];
                    }
                    else{
                        l1 = l3;
                    }
                }
            }
            s2.erase(ans[i]);
        }
    }
    return ans;
}

• 서브태스크 1: 20 / 20
• 서브태스크 2: 18 / 18
• 서브태스크 3: 11 / 11
• 서브태스크 4: 21 / 21
• 서브태스크 5: 30 / 30