Submission #1297033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297033		thesentro	Unscrambling a Messy Bug (IOI16_messy)	C++20	0 / 100	4 ms	6464 KiB

messy

#include <vector>
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
#define ll int
std::vector<int> restore_permutation(int n, int w, int r) {
    // add_element("0");
    // compile_set();
    // check_element("0");
    queue<pair<ll,ll>>q;
    // cout<<"JKLD"<<endl;
    q.push({0,n-1});
    vector<string>ret;
    while (!q.empty())
    {
        string s(n, '0');
        auto t = q.front();
        q.pop();
        ll le=t.first, ri = t.second;
        if (le==ri) continue;
        ll mid = (le+ri)/2;
        for (int i=t.first ; i<=mid ; i++)
            s[i] = '1';
        // cerr<<s<<endl;
        add_element(s);
        ret.push_back(s);
        q.push({le, mid});
        q.push({mid+1, ri});
    }
    compile_set();
    for (auto i:ret)
    {
        if (!check_element(i))
        {
            // cout<<"HEY"<<i<<endl;
            ll f1=-1,f2=-1;
            for (ll j=0 ; j<n ; j++)
            {
                if (i[j]=='1')
                {
                    if (f1==-1) f1 = j;
                    f2 = j;
                }
            }
            for (int j1=f1 ; j1<=f2 ; j1++)
            {
                for (int j2 =f2+1 ; j2<=f2-f1+1+f2 ; j2++)
                {
                    string s1 = i;
                    swap(s1[j1], s1[j2]);
                    if (check_element(s1))
                    {
                        vector<int>res(n);
                        for (int q=0 ; q<n ; q++) res[q] = q;
                        swap(res[j1], res[j2]);
                        return res;
                    }
                }
            }
        }
    }
}

Compilation message (stderr)

messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^
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: 0 / 20
• Subtask 2: 0 / 18
• Subtask 3: 0 / 11
• Subtask 4: 0 / 21
• Subtask 5: 0 / 30