oj.uz

Submission #54914

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

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 2 ms 376 KB Output is correct
2 Correct 4 ms 904 KB Output is correct
3 Correct 6 ms 1516 KB Output is correct
4 Correct 7 ms 1656 KB Output is correct
5 Correct 32 ms 3412 KB Output is correct
6 Correct 27 ms 3412 KB Output is correct
7 Correct 56 ms 6460 KB Output is correct
8 Correct 20 ms 6460 KB Output is correct
9 Correct 17 ms 6460 KB Output is correct
10 Correct 23 ms 6460 KB Output is correct
11 Correct 30 ms 6460 KB Output is correct
12 Correct 35 ms 6460 KB Output is correct
13 Correct 87 ms 9964 KB Output is correct
14 Correct 71 ms 11504 KB Output is correct
15 Incorrect 91 ms 16764 KB Output isn't correct
16 Execution timed out 258 ms 32868 KB Time limit exceeded
17 Execution timed out 352 ms 32876 KB Time limit exceeded
18 Runtime error 110 ms 32876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 127 ms 32876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 120 ms 32876 KB Execution killed with signal 11 (could be triggered by violating memory limits)