oj.uz

Submission #156448

# Submission time Handle Problem Language Result Execution time Memory
156448 2019-10-05T17:04:41 Z ionanghelina Drzava (COCI15_drzava) C++14
144 / 160
 1000 ms 9848 KB 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <cmath>

using namespace std;
using llint = long long;

#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

const int MAXN = 50010;
const int MAXK = 35;

int n, k, cookie;
int bio[MAXN];
vector<int> e[MAXN], val;

struct point {
  int x, y, cnt;

  point (int _x = 0, int _y = 0, int _cnt = 0) {
    x = _x;
    y = _y;
    cnt = _cnt;
  }

  friend bool operator < (const point& a, const point& b) {
    return a.x < b.x;
  }
} p[MAXN];

struct cmpf {
  bool operator()(const int& i, const int& j) {
    if (p[i].y != p[j].y) return p[i].y < p[j].y;
    return i > j;
  }
};

set<int, cmpf> s;
bool ok[MAXN][MAXK];

    inline int modulo (int x) { return x >= k ? x - k : x; }
    inline llint sqr(int x) { return (llint)x * x; }
    inline llint dist(int i, int j) {
      return sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y);
    }

bool findSubset(const vector<int>& vec) {
  int m = vec.size();
  if (m > k) return true;

  for (int mod = 0; mod < k; ++mod)
    ok[m][mod] = !mod;

  for (int i = m - 1; i >= 0; --i) {
    for (int mod = 0; mod < k; ++mod) {
      ok[i][mod] = ok[i + 1][mod];
      if (ok[i + 1][modulo(mod + vec[i])])
	ok[i][mod] = true;
    }
    if (ok[i + 1][vec[i]])
      return true;
  }

  return false;
}

void dfs(int x) {
  bio[x] = cookie;
  val.push_back(p[x].cnt);

  for (int y : e[x])
    if (bio[y] != cookie)
      dfs(y);
}

bool check(llint d) {
  int dsqrt = (double)(sqrt(d) + 1);
  for (int i = 0; i < n; ++i) {
    e[i].clear();
  }
  s.clear();

  int j = 0;
  for (int i = 0; i < n; ++i) {
    for (; p[i].x - p[j].x > d; ++j)
      s.erase(j);

    if (!s.empty()) {
      int inbox = 0;
      p[n] = point(p[i].x, p[i].y - dsqrt, 0);
      for (auto it = s.lower_bound(n); it != s.end(); ++it) {
	int idx = *it;

	if (p[idx].y > p[i].y + dsqrt) break;
	++inbox;
	if (inbox >= 8 * k) {
	  return true;
	}
	if (dist(i, idx) <= d) {
	  e[i].push_back(idx);
	  e[idx].push_back(i);
	}
      }
    }

    s.insert(i);
  }

  ++cookie;
  for (int i = 0; i < n; ++i)
    if (bio[i] != cookie) {
      val.clear();
      dfs(i);
      if (findSubset(val)) {
	return true;
      }
    }
  return false;
}

void init(void) {
  scanf("%d %d",&n,&k);
  for (int i = 0; i < n; ++i) {
    scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].cnt);
    p[i].cnt %= k;
  }
  sort(p, p + n);
}

void solve(void) {
  llint lo = 0, hi = 1e18, res = -1;
  while (lo <= hi) {
    llint mid = (lo + hi) / 2;
    if (check(mid)) {
      res = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  if (res == -1)
    printf("No solution!\n");
  else
    printf("%.3lf\n",sqrt(res));
}

int main(void) {
  init();
  solve();
  return 0;
}

Compilation message

drzava.cpp: In function 'void init()':
drzava.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&k);
   ~~~~~^~~~~~~~~~~~~~~
drzava.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].cnt);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 4 ms 2168 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 4 ms 2172 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 22 ms 2552 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 14 ms 2296 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 28 ms 2580 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 30 ms 2556 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2044 KB Output is correct
2 Correct 22 ms 2524 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 18 ms 2432 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 150 ms 3368 KB Output is correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Execution timed out 1061 ms 9848 KB Time limit exceeded

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Execution timed out 1064 ms 9680 KB Time limit exceeded

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 819 ms 7940 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 823 ms 8452 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 943 ms 9080 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 417 ms 5120 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 485 ms 6008 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2168 KB Output is correct
2 Correct 511 ms 6868 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2040 KB Output is correct
2 Correct 493 ms 6816 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2044 KB Output is correct
2 Correct 525 ms 5416 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2244 KB Output is correct
2 Correct 382 ms 5224 KB Output is correct