oj.uz

Submission #54913

# Submission time Handle Problem Language Result Execution time Memory
54913 2018-07-05T10:54:00 Z jklepec Printed Circuit Board (CEOI12_circuit) C++11
60 / 100
 100 ms 32992 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())

typedef long double lf;
typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e5 + 5, inf = 1e9;
const lf eps = 1e-12;

int x[MAXN], y[MAXN];

lf K;

lf kk(int X, int Y) {
  return (lf) Y / X;
}

struct duz {
  lf k, l;
  lf lo, hi;
  bool usp;

  duz() {}
  duz(int i, int j) {
    lo = kk(x[i], y[i]);
    hi = kk(x[j], y[j]);

    if(lo > hi) swap(lo, hi);

    if(x[i] == x[j]) {
      usp = true;
      k = x[i];
    }
    else {
      k = (lf) (y[i] - y[j]) / (x[i] - x[j]);
      l = (lf) y[i] - k * x[i];
      usp = false;
    }
  }

  friend bool operator < (const duz &A, const duz &B);
} line[MAXN];

lf calc(duz A) {
  if(A.usp) return A.k;
  return A.l / (K - A.k);
}

bool operator < (const duz &A, const duz &B) {

  lf x1 = calc(A), x2 = calc(B);
//
//  if(x1 == x2 && A.lo == K && B.lo == K) {
//    K += eps;
//    x1 = calc(A);
//    x2 = calc(B);
//    K -= eps;
//  }
//  else {
//    K -= eps;
//    x1 = calc(A);
//    x2 = calc(B);
//    K += eps;
//  }

  return x1 < x2;
}

vector<pair<lf, point> > e;

void add(int i, int j) {
  line[i] = duz(i, j);

  lf k1 = kk(x[i], y[i]);
  lf k2 = kk(x[j], y[j]);

  if(k1 > k2) swap(k1, k2);

  if(k1 == k2) return;

  e.push_back({k1 + eps, {0, i}});
  e.push_back({k2 - eps, {2, i}});
}

multiset<duz> s;
unordered_map<lf, int> m;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);

  int n; cin >> n;
  REP(i, n) {
    cin >> x[i] >> y[i];
    e.push_back({kk(x[i], y[i]), {1, i}});
    m[kk(x[i], y[i])] = max(m[kk(x[i], y[i])], inf - x[i]);
  }

  REP(i, n) {
    int j = (i + 1) % n;
    add(i, j);
  }

  sort(e.begin(), e.end());

  vector<int> sol(n, 0);
  for(auto p: e) {
    K = p.first;
    if(p.second.first == 0) {
      s.insert(line[p.second.second]);
    }
    if(p.second.first == 1) {
      if(sz(s) == 0) continue;
      duz X = *s.begin();
      if(calc(X) < x[p.second.second]) {
        sol[p.second.second] = true;
      }
    }
    if(p.second.first == 2) {
      if(s.find(line[p.second.second]) == s.end()) continue;
      s.erase(s.lower_bound(line[p.second.second]));
    }
  }

  vector<int> ans;
  REP(i, n) {
    if(!sol[i] && m[kk(x[i], y[i])] == inf - x[i]) ans.push_back(i);
  }

  cout << sz(ans) << endl;
  for(auto xx: ans) {
    cout << xx + 1 << " ";
  }
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 912 KB Output is correct
3 Correct 6 ms 1528 KB Output is correct
4 Correct 8 ms 1672 KB Output is correct
5 Correct 24 ms 3548 KB Output is correct
6 Correct 25 ms 3548 KB Output is correct
7 Correct 62 ms 6600 KB Output is correct
8 Incorrect 19 ms 6600 KB Output isn't correct
9 Correct 25 ms 6600 KB Output is correct
10 Correct 27 ms 6600 KB Output is correct
11 Correct 29 ms 6600 KB Output is correct
12 Correct 40 ms 6600 KB Output is correct
13 Incorrect 83 ms 9620 KB Output isn't correct
14 Correct 88 ms 11556 KB Output is correct
15 Execution timed out 102 ms 16676 KB Time limit exceeded
16 Execution timed out 246 ms 32992 KB Time limit exceeded
17 Execution timed out 349 ms 32992 KB Time limit exceeded
18 Runtime error 112 ms 32992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 146 ms 32992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 113 ms 32992 KB Execution killed with signal 11 (could be triggered by violating memory limits)