Submission #1310893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310893		matere	Unscrambling a Messy Bug (IOI16_messy)	C++20	100 / 100	2 ms	588 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> restore_permutation(int n, int w, int r){
    vector<int> cl(129);
    int cnt=n;
    while(cnt>1){
        for(int i=1;i<=n;i++){
            cl[i]=(i+cnt-1)/cnt;
        }
        cnt/=2;
        for(int cur=1;cur<=cl[n];cur++){
            string s="";
            for(int i=1;i<=n;i++){
                if(cl[i]!=cur) s+="1";
                else s+="0";
            }
            for(int i=1;i<=n;i++){
                if(cl[i]==cur){
                    for(int j=i;j<i+cnt;j++){
                        s[j-1]='1';
                        add_element(s);
                        s[j-1]='0';
                    }
                    break;
                }
            }
        }
    }
    compile_set();
    vector<int> ans(n+1),ans2(n+1);
    for(int i=1;i<=n;i++){
        ans[i]=0;
    }
    cnt=n;
    while(cnt>1){
        ans2=ans;
        vector<int>cl2;
        for(int cur=0;cur<cl[n];cur++){
            string s="";
            for(int i=1;i<=n;i++){
                if(ans[i]!=cur) s+="1";
                else s+="0";
            }
            for(int i=1;i<=n;i++){
                if(ans[i]==cur){
                    s[i-1]='1';
                    // cout<<s<<endl;
                    bool is=check_element(s);
                    ans2[i]*=2;
                    // cout<<s<<' ';
                    if(!is){
                        // cout<<'+';
                        ans2[i]++;
                    }
                    // cout<<endl;
                    s[i-1]='0';
                }
            }
        }
        ans=ans2;
        // for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
        // cout<<endl;
        cnt/=2;
    }
    ans.erase(ans.begin());
    return ans;
}

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