oj.uz

Submission #54907

# Submission time Handle Problem Language Result Execution time Memory
54907 2018-07-05T10:47:04 Z jklepec Printed Circuit Board (CEOI12_circuit) C++11
10 / 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) {
  return A.k < B.k;
  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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 7 ms 1592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 6 ms 2152 KB Output is correct
4 Correct 14 ms 2304 KB Output is correct
5 Incorrect 25 ms 4276 KB Output isn't correct
6 Incorrect 28 ms 4276 KB Output isn't correct
7 Incorrect 52 ms 7196 KB Output isn't correct
8 Incorrect 23 ms 7196 KB Output isn't correct
9 Runtime error 21 ms 7196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 26 ms 7196 KB Output isn't correct
11 Incorrect 24 ms 7652 KB Output isn't correct
12 Runtime error 46 ms 11880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Incorrect 88 ms 15508 KB Output isn't correct
14 Incorrect 70 ms 17552 KB Output isn't correct
15 Runtime error 109 ms 28136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 536 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Execution timed out 298 ms 33792 KB Time limit exceeded
18 Runtime error 95 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 112 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 143 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)