oj.uz

Submission #54916

# Submission time Handle Problem Language Result Execution time Memory
54916 2018-07-05T10:58:20 Z jklepec Printed Circuit Board (CEOI12_circuit) C++11
65 / 100
 100 ms 32884 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-8;

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
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 740 KB Output is correct
3 Correct 8 ms 1452 KB Output is correct
4 Correct 9 ms 1656 KB Output is correct
5 Correct 31 ms 3508 KB Output is correct
6 Correct 35 ms 3572 KB Output is correct
7 Correct 59 ms 6604 KB Output is correct
8 Correct 23 ms 6604 KB Output is correct
9 Correct 27 ms 6604 KB Output is correct
10 Correct 28 ms 6604 KB Output is correct
11 Correct 33 ms 6604 KB Output is correct
12 Correct 47 ms 6604 KB Output is correct
13 Correct 94 ms 9688 KB Output is correct
14 Execution timed out 112 ms 11580 KB Time limit exceeded
15 Execution timed out 120 ms 16752 KB Time limit exceeded
16 Execution timed out 243 ms 32884 KB Time limit exceeded
17 Execution timed out 377 ms 32884 KB Time limit exceeded
18 Runtime error 122 ms 32884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 130 ms 32884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 127 ms 32884 KB Execution killed with signal 11 (could be triggered by violating memory limits)