제출 #1368541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368541		bronze_coder	Unscrambling a Messy Bug (IOI16_messy)	C++20	70 / 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,0);
    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';
    }
    
    for(int i:l){
        vector<int> q;
        for(int j=0;j<n;j++){
            if(j!=i){
                s1[i] = '1';
                s1[j] = '1';
                if(check_element(s1)){
                    q.push_back(j);
                }
                s1[i] = '0';
                s1[j] = '0';
            }
        }
        int z = 0;
        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<<(n/2-1+a.size()-q.size()-z);
        for(int j:q){
            if(c[j]==0){
                ans[j] ^= ans[i];
            }
        }
    }
    return ans;
}

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