Submission #92018

#	Time	Username	Problem	Language	Result	Execution time	Memory
92018		Retro3014	Triangles (CEOI18_tri)	C++17	100 / 100	27 ms	2424 KiB

tri

#include "trilib.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int N;
vector<int> up, down;
deque<int> v1, v2;
vector<int> v;
deque<int> ans;
void merge_up(int x, int y){
    if(x==y)    return;
    int s=x, e=(x+y)/2+1;
    merge_up(s, e-1); merge_up(e, y);
    v1.clear(); v2.clear();
    for(int i=s; i<e; i++)  v1.push_back(up[i]);
    for(int i=e; i<=y; i++)  v2.push_back(up[i]);
    int idx=s;
    while((!v1.empty()) || (!v2.empty())){
        if(v1.empty()){
            up[idx++]=v2.front(); v2.pop_front();
        }else if(v2.empty()){
            up[idx++]=v1.front(); v1.pop_front();
        }else{
            if(is_clockwise(1, v1.front(), v2.front())){
                up[idx++] = v2.front();
                v2.pop_front();
            }else{
                up[idx++] = v1.front();
                v1.pop_front();
            }
        }
    }
    return;
}

void merge_down(int x, int y){
    if(x==y)    return;
    int s=x, e=(x+y)/2+1;
    merge_down(s, e-1); merge_down(e, y);
    v1.clear(); v2.clear();
    for(int i=s; i<e; i++)  v1.push_back(down[i]);
    for(int i=e; i<=y; i++)  v2.push_back(down[i]);
    int idx=s;
    while(!v1.empty() || !v2.empty()){
        if(v1.empty()){
            down[idx++]=v2.front(); v2.pop_front();
        }else if(v2.empty()){
            down[idx++]=v1.front(); v1.pop_front();
        }else{
            if(is_clockwise(1, v1.front(), v2.front())){
                down[idx++] = v2.front();
                v2.pop_front();
            }else{
                down[idx++] = v1.front();
                v1.pop_front();
            }
        }
    }
    return;
}

int main(){
    N=get_n();
    for(int i=3; i<=N; i++){
        if(is_clockwise(1, 2, i))   down.push_back(i);
        else    up.push_back(i);
    }
    if(!up.empty())merge_up(0, (int)up.size()-1);
    if(!down.empty())merge_down(0, (int)down.size()-1);
    v.push_back(2);
    for(int i=0; i<up.size(); i++){
        v.push_back(up[i]);
    }
    v.push_back(1);
    for(int i=0; i<down.size(); i++){
        v.push_back(down[i]);
    }
    ans.push_back(v[0]); ans.push_back(v[1]);
    for(int i=2; i<v.size(); i++){
        while(ans.size()>1 && is_clockwise(ans[ans.size()-2], ans.back(), v[i])) ans.pop_back();
        ans.push_back(v[i]);
    }
    int sz=(int)ans.size();
    while(sz--){
        int now=ans.front(); ans.pop_front();
        while(ans.size()>1 && is_clockwise(ans[ans.size()-2], ans.back(), now)) ans.pop_back();
        ans.push_back(now);
    }
    give_answer((int)ans.size());
    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<up.size(); i++){
                  ~^~~~~~~~~~
tri.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<down.size(); i++){
                  ~^~~~~~~~~~~~
tri.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=2; i<v.size(); i++){
                  ~^~~~~~~~~

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