Submission #430332

#	Time	Username	Problem	Language	Result	Execution time	Memory
430332		Amylopectin	Jousting tournament (IOI12_tournament)	C++14	100 / 100	166 ms	25156 KiB

tournament

#include <iostream>
#include <stdio.h>
#include <vector>
//#include "grader.cpp"
using namespace std;
const int mxn = 4e5 + 10,mxi = 1e9 + 10;
struct we
{
    int bef,ne;
};
vector <int> pa[mxn] = {};
struct we li[mxn] = {};
//,rmq[30][mxn] = {},cou = 1
int se[mxn] = {},pil[mxn] = {},ru,mse[mxn] = {},fva[mxn] = {},nn,ma = -1,mno = -1,fr[mxn] = {},to[mxn] = {},rr;
int fima(int l,int r)
{
    if(l > r)
        return l;
    return r;
}
int cre(int cl,int cr,int no)
{
    if(cl == cr)
    {
        se[no] = 1;
        return 0;
    }
    int mid = (cl+cr) / 2;
    cre(cl,mid,no*2);
    cre(mid+1,cr,no*2+1);
    se[no] = se[no*2] + se[no*2+1];
    return 0;
}
int del(int cl,int cr,int no,int tl,int tr)
{
    if(cr < tl || cl > tr)
    {
        return 0;
    }
    if(cl >= tl && cr <= tr)
    {
        se[no] = 0;
        return 0;
    }
    int mid = (cl+cr) / 2;
//    if(se[no*2] != 0)
//    {
        del(cl,mid,no*2,tl,tr);
//    }
//    if(se[no*2])
    del(mid+1,cr,no*2+1,tl,tr);
    se[no] = se[no*2] + se[no*2+1];
    return 0;
}
int fifr(int cl,int cr,int no,int cva)
{
    int mid = (cl+cr) / 2;
    if(cl == cr)
    {
        return cl;
    }
    if(se[no*2] >= cva)
    {
        return fifr(cl,mid,no*2,cva);
    }
    else
    {
        return fifr(mid+1,cr,no*2+1,cva - se[no*2]);
    }
}
int crema(int cl,int cr,int no)
{
    if(cl == cr)
    {
        mse[no] = fva[cl];
        return 0;
    }
    int mid = (cl+cr) / 2;
    crema(cl,mid,no*2);
    crema(mid+1,cr,no*2+1);
    mse[no] = fima(mse[no*2],mse[no*2+1]);
    return 0;
}
int sfima(int cl,int cr,int no,int tl,int tr)
{
    if(cr < tl || cl > tr)
    {
        return -1;
    }
    if(cl >= tl && cr <= tr)
    {
        return mse[no];
    }
    int mid = (cl+cr) / 2,cval,cvar;
    cval = sfima(cl,mid,no*2,tl,tr);
    cvar = sfima(mid+1,cr,no*2+1,tl,tr);
    return fima(cval,cvar);
}
int re(int cn,int acva)
{
    int i,fn,cva = 0;
    if(cn < nn)
    {
        if(acva > ma)
        {
            ma = acva;
            mno = cn;
        }
        return 0;
    }
    if(sfima(0,nn-2,1,fr[cn],to[cn]-1) < rr)
    {
        cva = 1;
    }
    for(i=0; i<pa[cn].size(); i++)
    {
        fn = pa[cn][i];
        re(fn,acva + cva);
    }
    return 0;
}
int GetBestPosition(int n, int nc, int r, int *k, int *st, int *en)
{
    nn = n;
    rr = r;
    int i,j,cf,ct,cn,cst = 0,cct;
    for(i=0; i<n; i++)
    {
        pil[i] = i;
        if(i < n-1)
            fva[i] = *(k+i);
        if(i == 0)
        {
            li[i] = {-1,i+1};
        }
        else if(i == n-1)
        {
            li[i] = {i-1,-1};
        }
        else
        {
            li[i] = {i-1,i+1};
        }
        fr[i] = i;
    }
    ru = n;
    cre(0,n-1,1);
    for(i=0; i<nc; i++)
    {
        cf = fifr(0,n-1,1,*(st+i) + 1);
        ct = fifr(0,n-1,1,*(en+i) + 1);
        fr[ru] = fr[cf];
        to[ru] = ct;
        fr[ct] = fr[cf];
        cct = ct;
        del(0,n-1,1,cf,ct-1);
        cf = pil[cf];
        ct = pil[ct];
        pil[cct] = ru;
        cn = cf;
        while(cn != ct)
        {
            pa[ru].push_back(cn);
            cn = li[cn].ne;
        }
        pa[ru].push_back(cn);
        if(cf == cst)
        {
            cst = ru;
            li[ru].bef = -1;
        }
        else
        {
            li[ru].bef = li[cf].bef;
            li[li[cf].bef].ne = ru;
        }
        if(li[ct].ne == -1)
        {
//            cst = ru;
            li[ru].ne = -1;
        }
        else
        {
            li[ru].ne = li[ct].ne;
            li[li[ct].ne].bef = ru;
        }

        ru ++;
    }
//    while(1)
//    {
//
//    }
    crema(0,n-2,1);
    re(ru-1,0);
    return mno;
}
//
//int main()
//{
//    cout << "Hello world!" << endl;
//    return 0;
//}

Compilation message (stderr)

tournament.cpp: In function 'int re(int, int)':
tournament.cpp:115:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(i=0; i<pa[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:126:11: warning: unused variable 'j' [-Wunused-variable]
  126 |     int i,j,cf,ct,cn,cst = 0,cct;
      |           ^

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51