Submission #559780

#	Time	Username	Problem	Language	Result	Execution time	Memory
559780		fcmalkcin	Meetings (JOI19_meetings)	C++17	0 / 100	38 ms	2888 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)
{

}
void Bridge(ll x,ll y)
{

}*/
ll rd(ll l,ll r)
{
    return abs((ll)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 ;
    }
    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)
            return ;
        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]);
    }
    bridge(vt1.back(),r);
    for (auto to:vt1)
    {
        dosth(gr[to]);
    }
}
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("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    vector<ll> p,p1,p2;
    cin>> n;
    for (int i=1; i<=n-1; i++)
    {
        ll x, y, w;
        cin>> x>> y>> w;
        p.pb(x);
        p1.pb(y);
        p2.pb(w);
    }
    vector<ll> res=minimum_closure_costs(n, p,p1,p2);
    for (auto to:res)
        cout <<to<<" ";
}*/

/*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:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=len; i<vt.size(); i++)
      |                     ~^~~~~~~~~~
meetings.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while (id1<vt1.size()&&id2<vt2.size())
      |            ~~~^~~~~~~~~~~
meetings.cpp:50:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while (id1<vt1.size()&&id2<vt2.size())
      |                            ~~~^~~~~~~~~~~
meetings.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     while (id1<vt1.size())
      |            ~~~^~~~~~~~~~~
meetings.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while (id2<vt2.size())
      |            ~~~^~~~~~~~~~~
meetings.cpp: In function 'void dosth(std::vector<int>)':
meetings.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i=0; i<vt1.size(); i++)
      |                   ~^~~~~~~~~~~

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