oj.uz

Submission #54915

# Submission time Handle Problem Language Result Execution time Memory
54915 2018-07-05T10:57:46 Z jklepec Printed Circuit Board (CEOI12_circuit) C++11
70 / 100
 100 ms 32892 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-7;

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}});
  //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
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 908 KB Output is correct
3 Correct 10 ms 1416 KB Output is correct
4 Correct 11 ms 1544 KB Output is correct
5 Correct 26 ms 3392 KB Output is correct
6 Correct 28 ms 3420 KB Output is correct
7 Correct 59 ms 6460 KB Output is correct
8 Correct 22 ms 6460 KB Output is correct
9 Correct 22 ms 6460 KB Output is correct
10 Correct 33 ms 6460 KB Output is correct
11 Correct 32 ms 6460 KB Output is correct
12 Correct 52 ms 6460 KB Output is correct
13 Correct 99 ms 9688 KB Output is correct
14 Correct 87 ms 11656 KB Output is correct
15 Execution timed out 113 ms 16804 KB Time limit exceeded
16 Execution timed out 230 ms 32892 KB Time limit exceeded
17 Execution timed out 355 ms 32892 KB Time limit exceeded
18 Runtime error 135 ms 32892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 130 ms 32892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 123 ms 32892 KB Execution killed with signal 11 (could be triggered by violating memory limits)