oj.uz

Submission #972472

# Submission time Handle Problem Language Result Execution time Memory
972472 2024-04-30T13:21:47 Z Charizard2021 Triangles (CEOI18_tri) C++17
0 / 100
 1 ms 604 KB 
#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
vector<int> orderDivide(vector<int> points){
    if((int)points.size() <= 1){
        return points;
    }
    int cur = points[rand() % (int)points.size()];
    vector<int> leftHalf;
    vector<int> rightHalf;
    for(int i = 0; i < (int)points.size(); i++){
        if(points[i] != cur){
            if(is_clockwise(1, cur, points[i])){
                rightHalf.push_back(points[i]);
            }
            else{
                leftHalf.push_back(points[i]);
            }
        }
    }
    vector<int> leftorderDivide = orderDivide(leftHalf);
    vector<int> rightorderDivide = orderDivide(rightHalf);
    leftorderDivide.push_back(cur);
    for(int a : rightorderDivide){
        leftorderDivide.push_back(a);
    }
    return leftorderDivide;
}
int main(){
    int n = get_n();
    vector<int> points;
    for(int i = 2; i <= n; i++){
        points.push_back(i);
    }
    points = orderDivide(points);
    points.insert(points.begin(), 1);
    vector<int> cur;
    cur.push_back(1);
    for(int i = 1; i < (int)points.size(); i++){
        while((int)cur.size() >= 2 && !is_clockwise(cur[(int)cur.size() - 2], cur.back(), points[i])){
            cur.pop_back();
        }
        cur.push_back(points[i]);
    }
    deque<int> dq;
    for(int i = 0; i < (int)points.size(); i++){
        dq.push_back(points[i]);
    }
    while(true){
        bool works = true;
        int cur = dq.back();
        dq.pop_back();
        if(is_clockwise(dq.back(), cur, dq.front())){
            dq.push_back(cur);
        }
        else{
            works = false;
        }
        cur = dq.front();
        dq.pop_front();
        if(is_clockwise(dq.back(), cur, dq.front())){
            dq.push_front(cur);
        }
        else{
            works = false;
        }
        if(works){
            break;
        }
    }
    give_answer(dq.size());
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -