Submission #1363381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363381		BigBadBully	Voltage 2 (JOI26_voltage)	C++20	54 / 100	45 ms	676 KiB

voltage

#include <bits/stdc++.h>
#include "voltage.h"
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
bool solve(int n, int m) {
    
    vector<int> vis(n,0);
    vector<pii> edg;
    while(edg.size()<m)
    {
        int mini = 0;
        int eq = 1;
        while(vis[mini])mini++;
        for(int i = mini+1; i < n ;i++)
            if(!vis[i])
            {
                vector<int> a = vis;
                auto b = a;
                a[mini] = 1;
                b[i] = 1;
                int res = query(a,b);
                if(res<0)
                    mini = i;
                if(res!=0)eq = 0;
            }
        if(eq)return false;
        vis[mini]=1;
        vector<int> left;
        for(int i = 0; i < n; i++)
            if(!vis[i])left.push_back(i);
        random_shuffle(left.begin(),left.end());
        int k = left.size();
        function<int(int,int)> ask = [&](int l,int r)
        {
            if(r==k)return -1;
            auto a = vis,b = vis;
            a[mini] = 0;
            for(int i = l; i <= r;i++)
                a[left[i]]=b[left[i]]=1;
            return query(a,b);
        };
        function<int(int)> fnd = [&](int idx)
        {
            int l = idx,r = k;
            if(ask(l,k-1)==0)return k;
            while(r-l)
            {
                int mid = l +r>>1;
                int res = ask(idx,mid);
                if(res==1)return -3;
                if(ask(idx,mid)==-1)
                    r = mid;
                else
                    l = mid+1;
            }
            return l;
        };
        int cur = -1;
        while(cur >= -1 && cur < k)
        {
            cur = fnd(cur+1);
            if(cur>=0&&cur<k)
                edg.push_back({left[cur],mini});
        }
        if(cur<0)
            return false;
        /*for(int i = 0;i  < n; i++)
            if(!vis[i])
            {
                auto a = vis,b = vis;
                a[mini]=0;
                a[i]=1;
                b[i]=1;
                int res = query(a,b);
                if(res>0)return false;
                if(res)
                    edg.push_back({i,mini});
            }*/
    }
    if(edg.size()>m)
        return false;
    for(pii x:edg)
    answer(x.ff,x.ss);
    return true;
}

Compilation message (stderr)

voltage.cpp: In function 'bool solve(int, int)':
voltage.cpp:33:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   33 |         random_shuffle(left.begin(),left.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from voltage.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 27 / 27
• Subtask 4: 0 / 18
• Subtask 5: 17 / 17
• Subtask 6: 0 / 16