Submission #559802

#	Time	Username	Problem	Language	Result	Execution time	Memory
559802		fcmalkcin	Meetings (JOI19_meetings)	C++17	100 / 100	713 ms	3300 KiB

meetings

#include <bits/stdc++.h>
using namespace std;

#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+50;
const ll mod=1e9+7  ;
const ll base=1e18;

#include "meetings.h"

/// i believe myself
/// goal 1/7
/*ll Query(ll l,ll r,ll t)
{
    cout <<l<<" "<<r<<" "<<t<<endl;
    ll x;
    cin>> x;
    return x;
}
void Bridge(ll x,ll y)
{
    cout <<"! "<<x<<" "<<y<<endl;
}*/
long long rd(long long l,long long r)
{
    return abs((long long)rnd())%(r-l+1)+l;
}
vector<ll> gr[maxn];
ll st;
vector<ll> dosth1(vector<ll> vt)
{
    if (vt.size()<=1)
        return vt;
    vector<ll> vt1;
    vector<ll> vt2;
    ll len=vt.size()/2;
    for (int i=0; i<len; i++)
        vt1.pb(vt[i]);
    for (int i=len; i<vt.size(); i++)
        vt2.pb(vt[i]);
    vt1=dosth1(vt1);
    vt2=dosth1(vt2);
    ll id1=0;
    ll id2=0;
    vector<ll> res;
    while (id1<vt1.size()&&id2<vt2.size())
    {
        if (Query(st,vt1[id1],vt2[id2])==vt1[id1])
            res.pb(vt1[id1]),id1++;
        else
            res.pb(vt2[id2]),id2++;
    }
    while (id1<vt1.size())
    {
        res.pb(vt1[id1]),id1++;
    }
    while (id2<vt2.size())
    {
        res.pb(vt2[id2]),id2++;
    }
    return res;
}
void bridge(ll x,ll y)
{
    if (x>y)
        swap(x,y);
    Bridge(x,y);
}
void dosth(vector<ll> vt)
{
    if (vt.size()<=1)
        return ;
    if (vt.size()==2)
    {
        bridge(vt[0],vt[1]);
        return ;
    }
    //  cout <<vt.size()<<" wtf"<<endl;
    ll n=vt.size();
    ll l=rd(0,n-1);
    ll r=rd(0,n-1);
    while (r==l)
        r=rd(0,n-1);
    l=vt[l];
    r=vt[r];
    vector<ll> vt1;
    st=l ;
    for (auto to:vt)
    {
        if (to==l||to==r)
            continue;
        ll h=Query(l,r,to);
        if (h==to)
        {
            vt1.pb(to);
        }
        else
        {
            gr[h].pb(to);
        }
    }
    vt1=dosth1(vt1);
    for (int i=0; i<vt1.size(); i++)
    {
        if (i==0)
            bridge(vt1[i],st);
        else
            bridge(vt1[i],vt1[i-1]);
    }
    if (vt1.size())
        bridge(vt1.back(),r);
    else
        bridge(l,r);
    vt1.pb(l);
    vt1.pb(r);
    for (auto to:vt1)
    {
        if (gr[to].size())
        {
            vector<ll> vt2=gr[to];
            vt2.pb(to);
            gr[to].clear();
            dosth(vt2);
        }
    }
}
void Solve(ll n)
{
    vector<ll> vt;
    for (int i=0; i<=n-1; i++)
        vt.pb(i);
    dosth(vt);
}
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    Solve(5);
}*/

/*5
0 1 1
0 2 4
0 3 3
2 4 2
*/

Compilation message (stderr)

meetings.cpp:14:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const ll base=1e18;
      |               ^~~~
meetings.cpp: In function 'std::vector<int> dosth1(std::vector<int>)':
meetings.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=len; i<vt.size(); i++)
      |                     ~^~~~~~~~~~
meetings.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while (id1<vt1.size()&&id2<vt2.size())
      |            ~~~^~~~~~~~~~~
meetings.cpp:53:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while (id1<vt1.size()&&id2<vt2.size())
      |                            ~~~^~~~~~~~~~~
meetings.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     while (id1<vt1.size())
      |            ~~~^~~~~~~~~~~
meetings.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     while (id2<vt2.size())
      |            ~~~^~~~~~~~~~~
meetings.cpp: In function 'void dosth(std::vector<int>)':
meetings.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=0; i<vt1.size(); i++)
      |                   ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71