Submission #704296

#	Time	Username	Problem	Language	Result	Execution time	Memory
704296		Hiennoob123	Park (JOI17_park)	C++14	0 / 100	1088 ms	684 KiB

park

#include "park.h"
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const ll maxn = 1405;
static int Place[1400];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l ,ll r)
{
    ll x = rng();
    return (abs(x)%(r-l+1)+l);
}
ll t, n;
vector<pll> Edge;
ll par[maxn];
ll find_par(ll v)
{
    if(v==par[v]) return v;
    else return par[v] = find_par(par[v]);
}
bool mid(ll a, ll b, ll c)
{
    if(a>c) swap(a, c);
    //cout << a << " " << b << " " << c << "\n";
    for(int i = 0; i< n; i++) Place[i] = 1;
    Place[b] = 0;
    return !Ask(a, c, Place);
}
bool adj(ll a, ll b)
{
    if(a>b) swap(a, b);
    //cout << a << " " << b << "\n";
    for(int i = 0; i< n; i++) Place[i] = 0;
    Place[a] = Place[b] = 1;
    return Ask(a, b, Place);
}
vector<ll> solve(vector<ll> &A)
{
    if(A.size()==1)
    {
        vector<ll> X;
        X.push_back(A[0]);
        return X;
    }
    else if(A.size()==2)
    {
        Edge.push_back(mp(A[0], A[1]));
        vector<ll> X;
        X.push_back(A[0]);
        X.push_back(A[1]);
        return X;
    }
    vector<vector<ll>> T;
    swap(A[0], A[random(0, A.size()-1)]);
    if(A.size()==5)
    {
        for(int i = 0; i< A.size(); i++)
        {
            if(A[i]==0) swap(A[i], A[0]);
        }
    }
    //random_shuffle(A.begin(), A.end());
    //for(auto u: A) cout << u << " ";
    //cout << "\n-1 " << A[0] << "\n";
    ll root = A[0];
    for(int i = 1; i< A.size(); i++)
    {
        for(int j = 0; j<= T.size(); j++)
        {
            if(j==T.size())
            {
                T.emplace_back();
                T[T.size()-1].push_back(A[i]);
                break;
            }
            else
            {
                if(mid(T[j][0], root, A[i])) continue;
                else
                {
                    T[j].push_back(A[i]);
                    break;
                }
            }
        }
    }
    vector<ll> save;
    for(int i = 0; i< T.size(); i++)
    {
        vector<ll> ss = solve(T[i]);
        ll value = -1;
        for(auto u: ss)
        {
            //cout << root << " " << u << "\n";
            if(adj(u, root))
            {
                value = u;
                Edge.push_back(mp(u, root));
                break;
            }
        }
        for(auto u: ss)
        {
            if(u==value&&T[i].size()!=1) continue;
            save.push_back(u);
        }
    }
    return save;
}
void Detect(int xaa, int xa) {
    t = xaa; n = xa;
    vector<ll> T;
    for(int i = 0; i< n; i++) T.push_back(i);
    T = solve(T);
    //cout << Edge.size() << "\n";
    for(auto u: Edge)
    {
        if(u.fi>u.se) swap(u.fi, u.se);
        //cout << u.fi << " " << u.se << "\n";
        Answer(u.fi, u.se);
    }
}

Compilation message (stderr)

park.cpp: In function 'std::vector<int> solve(std::vector<int>&)':
park.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int i = 0; i< A.size(); i++)
      |                        ~^~~~~~~~~~
park.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 1; i< A.size(); i++)
      |                    ~^~~~~~~~~~
park.cpp:74:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int j = 0; j<= T.size(); j++)
      |                        ~^~~~~~~~~~~
park.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             if(j==T.size())
      |                ~^~~~~~~~~~
park.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i< T.size(); i++)
      |                    ~^~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23