oj.uz

Submission #54906

# Submission time Handle Problem Language Result Execution time Memory
54906 2018-07-05T10:45:45 Z jklepec Printed Circuit Board (CEOI12_circuit) C++11
5 / 100
 100 ms 33792 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-9;

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);

  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) {
      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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 6 ms 1596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 6 ms 2148 KB Output is correct
4 Runtime error 11 ms 3028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 23 ms 6864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 29 ms 6948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 52 ms 12948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 18 ms 12948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 27 ms 12948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 31 ms 12948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 28 ms 12948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 40 ms 12948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 91 ms 19136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 78 ms 22864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 103 ms 28100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 504 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 609 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 96 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 114 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 119 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)