oj.uz

Submission #54908

# Submission time Handle Problem Language Result Execution time Memory
54908 2018-07-05T10:48:58 Z jklepec Printed Circuit Board (CEOI12_circuit) C++11
45 / 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
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Execution timed out 1077 ms 1200 KB Time limit exceeded
3 Correct 8 ms 1756 KB Output is correct
4 Correct 7 ms 2068 KB Output is correct
5 Correct 29 ms 3868 KB Output is correct
6 Correct 26 ms 3868 KB Output is correct
7 Correct 60 ms 6956 KB Output is correct
8 Correct 25 ms 6956 KB Output is correct
9 Runtime error 30 ms 6956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 21 ms 6956 KB Output is correct
11 Correct 27 ms 7604 KB Output is correct
12 Execution timed out 1087 ms 9260 KB Time limit exceeded
13 Runtime error 83 ms 19152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 73 ms 20976 KB Output is correct
15 Execution timed out 1080 ms 26124 KB Time limit exceeded
16 Execution timed out 1081 ms 33792 KB Time limit exceeded
17 Execution timed out 321 ms 33792 KB Time limit exceeded
18 Runtime error 114 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 118 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 121 ms 33792 KB Execution killed with signal 11 (could be triggered by violating memory limits)