제출 #1363424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363424		BigBadBully	Voltage 2 (JOI26_voltage)	C++20	22 / 100	19 ms	940 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;
    vector<int> id(n);
    iota(id.begin(),id.end(),0);
    function<bool(int,int)> cmp = [&](int a,int b){
        auto f=vis,s=vis;
        f[a]=1;
        s[b]=1;
        return query(f,s)==1;
    
    };
    sort(id.begin(),id.end(),cmp);
    int itera = 0;
    while(edg.size()<m)
    {
        int mini = id[itera++];
        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;
        vector<int> mile;
        vector<int> seen(n,0);
        while(cur >= -1 && cur < k)
        {
            cur = fnd(cur+1);
            if(cur>=0&&cur<k)
                edg.push_back({left[cur],mini}),seen[left[cur]]=1;
        }
        if(cur<0)
            return false;
        while(1)
        {
            bool did = 0;
            int cnt = 0;
            for(int it = 0;it < n;it++)
            {
                int i = id[it];
                if(seen[i])
                {
                    int l = -1,r =cnt-1;
                    while(r-l)
                    {
                        int mid = l+r+1>>1;
                        if(vis[id[mid]]||cmp(id[mid],i))
                            l = mid;
                        else
                            r = mid-1;
                    }
                    id.erase(id.begin()+cnt);
                    id.insert(id.begin()+l+1,i);
                    seen[i]=0;
                    did = 1;
                    break;
                }
                cnt++;
            }
            if(!did)break;
        }
        /*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;
}

컴파일 시 표준 에러 (stderr) 메시지

voltage.cpp: In function 'bool solve(int, int)':
voltage.cpp:29: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]
   29 |         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)
      |     ^~~~~~~~~~~~~~

• 서브태스크 0: 0 / 0
• 서브태스크 1: 10 / 10
• 서브태스크 2: 12 / 12
• 서브태스크 3: 0 / 27
• 서브태스크 4: 0 / 18
• 서브태스크 5: 0 / 17
• 서브태스크 6: 0 / 16