oj.uz

Submission #972537

# Submission time Handle Problem Language Result Execution time Memory
972537 2024-04-30T14:27:37 Z MilosMilutinovic Triangles (CEOI18_tri) C++14
0 / 100
 170 ms 262144 KB 
#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 + 1; 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

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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 164 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -