제출 #348423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348423		daniel920712	마상시합 토너먼트 (IOI12_tournament)	C++14	17 / 100	1074 ms	2412 KiB

tournament

#include <stdio.h>
#include <time.h>
#include <iostream>
#include <stdio.h>
#include <assert.h>
using namespace std;
struct A
{
    int nxl,nxr;
    int here;
    int big,sz;
}Node[1000005];
int now=0;
void UPD(int here)
{
    Node[here].sz=Node[Node[here].nxl].sz+Node[Node[here].nxr].sz+1;
    Node[here].big=max(max(Node[Node[here].nxl].big,Node[Node[here].nxr].big),Node[here].here);
}
int Merge(int l,int r,int con)
{
    if(l==0) return r;
    if(r==0) return l;
    if((long long) rand()*(long long) (Node[l].sz+Node[r].sz)<=(long long) RAND_MAX*(long long) Node[l].sz)
    {
        Node[l].nxr=Merge(Node[l].nxr,r,con+1);
        UPD(l);
        return l;
    }
    else
    {
        Node[r].nxl=Merge(l,Node[r].nxl,con+1);
        UPD(r);
        return r;
    }
}
pair < int , int > Split(int here,int con)
{
    pair < int , int > t;
    if(here==0) return make_pair(0,0);
    if(con<=Node[Node[here].nxl].sz)
    {
        t=Split(Node[here].nxl,con);
        Node[here].nxl=t.second;
        UPD(here);
        t.second=here;
        return t;
    }
    else
    {
        t=Split(Node[here].nxr,con-Node[Node[here].nxl].sz-1);
        Node[here].nxr=t.first;
        UPD(here);
        t.first=here;
        return t;
    }
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    int ans=-1,where=-1,now=1,root=0,i,j,tt;
    pair < int , int > t,t2;
    srand(time(NULL));
    Node[0].sz=0;
    Node[0].big=-1;
    for(i=0;i<N;i++)
    {
        now=1;
        root=0;
        tt=0;
        for(j=0;j<i;j++)
        {
            Node[now].big=K[j];
            Node[now].here=K[j];
            Node[now].nxl=0;
            Node[now].nxr=0;
            Node[now].sz=1;

            root=Merge(root,now,0);
            now++;
        }
        Node[now].big=R;
        Node[now].here=R;
        Node[now].nxl=0;
        Node[now].nxr=0;
        Node[now].sz=1;
        root=Merge(root,now,0);
        now++;
        for(j=i;j<N-1;j++)
        {
            Node[now].big=K[j];
            Node[now].here=K[j];
            Node[now].nxl=0;
            Node[now].nxr=0;
            Node[now].sz=1;
            root=Merge(root,now,0);
            now++;
        }
        //if(N>1000) continue;
        for(j=0;j<C;j++)
        {
            t=Split(root,S[j]);
            t2=Split(t.second,E[j]-S[j]+1);
            Node[now].big=Node[t2.first].big;
            Node[now].here=Node[t2.first].big;
            if(Node[now].big==R) tt++;
            Node[now].nxl=0;
            Node[now].nxr=0;
            Node[now].sz=1;
            root=Merge(Merge(t.first,now,0),t2.second,0);
            now++;
        }
        if(tt>ans)
        {
            ans=tt;
            where=i;
        }
    }

    return where;

}

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