Submission #972541

#	Time	Username	Problem	Language	Result	Execution time	Memory
972541		MilosMilutinovic	Triangles (CEOI18_tri)	C++14	100 / 100	866 ms	85972 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n = get_n();
  map<array<int, 3>, bool> mp;
  auto Ask = [&](int i, int j, int k) {
    if (mp.count({i, j, k})) {
      return mp[{i, j, k}];
    }
    mp[{i, j, k}] = is_clockwise(i, j, k);
    mp[{k, j, i}] = !mp[{i, j, k}];
    return mp[{i, j, k}];
  };
  vector<vector<int>> pts(2);
  for (int i = 3; i <= n; i++) {
    pts[!Ask(1, 2, i)].push_back(i);
  }
  pts[1].push_back(2);
  for (int it = 0; it < 2; it++) {
    function<vector<int>(vector<int>)> Solve = [&](vector<int> vec) {
      if (vec.size() <= 1) {
        return vec;
      }
      int len = (int) vec.size();
      int mid = len / 2;
      vector<int> L, R;
      for (int i = 0; i < mid; i++) {
        L.push_back(vec[i]);
      }
      for (int i = mid; i < len; i++) {
        R.push_back(vec[i]);
      }
      L = Solve(L);
      R = Solve(R);
      vector<int> res;
      int pl = 0, pr = 0;
      while (pl < L.size() || pr < R.size()) {
        if (pl == L.size()) {
          res.push_back(R[pr]);
          ++pr;
        } else if (pr == R.size()) {
          res.push_back(L[pl]);
          ++pl;
        } else if (!Ask(1, L[pl], R[pr])) {
          res.push_back(L[pl]);
          ++pl;
        } else {
          res.push_back(R[pr]);
          ++pr;
        }
      }
      return res;
    };
    pts[it] = Solve(pts[it]);
  }
  vector<int> v;
  for (int i : pts[1]) {
    v.push_back(i);
  }
  v.push_back(1);
  for (int i : pts[0]) {
    v.push_back(i);
  }
  vector<int> res;
  int bef = 0;
  for (int it = 0; it < 2; it++) {
    bef = (int) res.size();
    for (int i : v) {
      while (res.size() >= 2 && Ask(res.rbegin()[1], res.back(), i)) {
        res.pop_back();
      }
      res.push_back(i);
    }
  }
  cout << (int) res.size() - bef << endl;
  return 0;
}

Compilation message (stderr)

tri.cpp: In lambda function:
tri.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |       while (pl < L.size() || pr < R.size()) {
      |              ~~~^~~~~~~~~~
tri.cpp:42:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |       while (pl < L.size() || pr < R.size()) {
      |                               ~~~^~~~~~~~~~
tri.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (pl == L.size()) {
      |             ~~~^~~~~~~~~~~
tri.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         } else if (pr == R.size()) {
      |                    ~~~^~~~~~~~~~~

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