Submission #1135905

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

messy

#include <vector>
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
#ifdef t9unkubj
namespace judge{
void add_element(string x);
void compile_set();
bool check_element(string x);
};
using namespace judge;
#else 
#include"messy.h"
#endif
std::vector<int> restore_permutation(int n, int w, int r) {
    int d=0;
    while((1<<d)<n)d++;
    vc<int>to(n);
    int G=n/4;
    rep(i,d){
        if(i==0){
            rep(j,n/2){    
                string send(n,'0');
                send[j]='1';
                add_element(send);
                to[j]|=1<<i;
            }
        }else if(i==1){
            rep(j,n/4){    
                string send(n,'1');
                send[j]='0';
                add_element(send);
                to[j]|=1<<i;
            }
            REP(j,n/2,n/4*3){    
                string send(n,'1');
                send[j]='0';
                add_element(send);
                to[j]|=1<<i;
            }
        }else{
            REP(k,1,n/G){
                int l=k*G,r=(k+1)*G;
                REP(j,l,(l+r)/2){
                    string send(n,'0');    
                    rep(j,G)send[j]='1';
                    send[j]='1';
                    add_element(send);
                    to[j]|=1<<i;
                }
            }
            rep(j,G/2){
                string send(n,'0');    
                REP(j,G,G+G)send[j]='1';
                send[j]='1';
                add_element(send);
                to[j]|=1<<i;
            }
            G/=2;
        }
    }
    dbg(to);
    compile_set();
    vc<int>ans(n);
    vc<int>cnt(n);
    rep(i,n){
        string send(n,'0');
        send[i]='1';
        cnt[i]|=check_element(send);
    }
    rep(i,n){
        string send(n,'1');
        send[i]='0';
        cnt[i]|=check_element(send)<<1;
    }

    set<int>ones;
    set<int>twos;
    rep(i,n){
        if(cnt[i]==3){
            ones.insert(i);
        }else if(cnt[i]==(to[n>>2]&3))twos.insert(i);
    }
    REP(i,2,d){
        rep(j,n){
            if(ones.count(j)){
                string send(n,'0');
                for(auto&i:twos)send[i]='1';
                send[j]='1';
                cnt[j]|=check_element(send)<<i;
            }else{
                string send(n,'0');
                for(auto&i:ones)send[i]='1';
                send[j]='1';
                cnt[j]|=check_element(send)<<i;
            }
        }
        ones.clear();
        twos.clear();
        int M=(1<<(i+1))-1;
        int M2=to[(n>>(i+1))]&M;
        rep(i,n){
            if(cnt[i]==M)ones.insert(i);
            else if(cnt[i]==M2)twos.insert(i);
        }
    }
    vc<int>inv(n);
    rep(i,n)inv[to[i]]=i;
    rep(i,n)cnt[i]=inv[cnt[i]];
    return cnt;
}
namespace judge{
    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;
    }
    void clear(){
        set_.clear();
        compiled=false;
        n=0;
        p.clear();
        w=0;
        r=0;
    }
}

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) {
    dbg(x);
    if (--w < 0 || compiled || !check(x)) {
        wa();
    }
    set_.insert(x);
}

bool check_element(string x) {
    if (--r < 0 || !compiled || !check(x)) {
        wa();
    }
    return set_.count(x);
}

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;
}

void run(){
    clear();
    cin>>n;
    p.resize(n);
    rep(i,n)cin>>p[i];
    w=r=1024;
    dbg(restore_permutation(n,w,r));
}
};
//+int main(){judge::run();}
/*
16
0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15
*/

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