Submission #1161286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161286		12345678	Triangles (CEOI18_tri)	C++20	100 / 100	14 ms	1472 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

const int nx=4e4+5;

int n, cnt, qrs, lsz, rsz, tmp[nx];
vector<int> l, r;
deque<int> dl, dr;

void mergesort(int l, int r, int st, vector<int> &x)
{
    if (l==r) return;
    int md=(l+r)/2, idxl=l, idxr=md+1, idx=l;
    mergesort(l, md, st, x);
    mergesort(md+1, r, st, x);
    while (idx<=r)
    {
        //cout<<"debug "<<l<<' '<<r<<' '<<idxl<<' '<<idxr<<'\n';
        if (idxl>md) tmp[idx++]=x[idxr++];
        else if (idxr>r) tmp[idx++]=x[idxl++];
        else if (is_clockwise(st, x[idxl], x[idxr])) tmp[idx++]=x[idxl++];
        else tmp[idx++]=x[idxr++];
    }
    for (int i=l; i<=r; i++) x[i]=tmp[i];
}

int main()
{
    n=get_n();
    for (int i=3; i<=n; i++)
    {
        if (is_clockwise(1, 2, i)) r.push_back(i);
        else l.push_back(i);
    }
    lsz=l.size();
    rsz=r.size();
    if (lsz) mergesort(0, lsz-1, 1, l);
    if (rsz) mergesort(0, rsz-1, 2, r);
    dl.push_back(1);
    for (int i=0; i<lsz; i++)
    {
        while (dl.size()>=2&&!is_clockwise(dl[dl.size()-2], dl.back(), l[i])) dl.pop_back();
        dl.push_back(l[i]);
    }
    dr.push_back(2);
    for (int i=0; i<rsz; i++)
    {
        while (dr.size()>=2&&!is_clockwise(dr[dr.size()-2], dr.back(), r[i])) dr.pop_back();
        dr.push_back(r[i]);
    }
    while (1)
    {
        if (dl.size()>=2&&dr.size()>=1&&!is_clockwise(dr.back(), dl[0], dl[1]))
        {
            dl.pop_front();
            continue;
        }
        if (dl.size()>=1&&dr.size()>=2&&!is_clockwise(dr[dr.size()-2], dr.back(), dl[0]))
        {
            dr.pop_back();
            continue;
        }
        if (dl.size()>=2&&dr.size()>=1&&!is_clockwise(dl[dl.size()-2], dl.back(), dr[0]))
        {
            dl.pop_back();
            continue;
        }
        if (dl.size()>=1&&dr.size()>=2&&!is_clockwise(dl.back(), dr[0], dr[1]))
        {
            dr.pop_front();
            continue;
        }
        break;
    }
    give_answer(dl.size()+dr.size());
    return 0;
}

/*
g++ tri3.cpp trilib.h trilib.c -o b
6
1 1
4 3
2 2
1 4
5 1
3 2
*/

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25