oj.uz

답안 #54911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54911 2018-07-05T10:52:14 Z jklepec Printed Circuit Board (CEOI12_circuit) C++11
55 / 100
 100 ms 32984 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) {
      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
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 416 KB Output isn't correct
2 Correct 4 ms 868 KB Output is correct
3 Correct 7 ms 1556 KB Output is correct
4 Correct 9 ms 1760 KB Output is correct
5 Correct 27 ms 3612 KB Output is correct
6 Correct 26 ms 3612 KB Output is correct
7 Correct 60 ms 6700 KB Output is correct
8 Correct 23 ms 6700 KB Output is correct
9 Incorrect 22 ms 6700 KB Output isn't correct
10 Correct 25 ms 6700 KB Output is correct
11 Correct 31 ms 6700 KB Output is correct
12 Correct 38 ms 6700 KB Output is correct
13 Incorrect 77 ms 9672 KB Output isn't correct
14 Correct 87 ms 11592 KB Output is correct
15 Execution timed out 105 ms 16748 KB Time limit exceeded
16 Execution timed out 258 ms 32984 KB Time limit exceeded
17 Execution timed out 353 ms 32984 KB Time limit exceeded
18 Runtime error 115 ms 32984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 115 ms 32984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 123 ms 32984 KB Execution killed with signal 11 (could be triggered by violating memory limits)