Submission #87752

#	Time^UTC-0	Username	Problem	Language	Result	Execution time	Memory
87752	2018-12-02 09:30:31	JustInCase	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1914 ms	412836 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

bitaro

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
Solution:
  Idea: We can precompute for each node the sqrt(n) furthest nodes with a simple dp. Then for each query
if the number of forbidden nodes is less than sqrt(n) then for sure the answer will be among the precomputed
otherwise we can simply solve it with a brutefore since the queries of this type will be less than sqrt(n).
*/
#include <bits/stdc++.h>
const int32_t MAX_N = 1e5;
const int32_t BUCKET_SIZE = 300;
const int32_t INF = 2e9;
bool isInVector[MAX_N + 5];
bool isForbidden[MAX_N + 5];
std::vector< std::pair< int32_t, int32_t > > Merge(const std::vector< std::pair< int32_t, int32_t> > &v1, 
    const std::vector< std::pair< int32_t, int32_t > > &v2) {
  std::vector< std::pair< int32_t, int32_t > > ans;
  int32_t ind1 = 0, ind2 = 0;
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
    if(ind1 < v1.size()) {
      if(ind2 < v2.size()) {
        if(v1[ind1].first >= v2[ind2].first + 1) {
          if(!isInVector[v1[ind1].second]) {
            isInVector[v1[ind1].second] = true;
            ans.push_back(v1[ind1]);
          }
          ind1++;
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > Merge(const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
bitaro.cpp:21:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
         ~~~~~^~~~~~~~~~~
bitaro.cpp:21:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
                             ~~~~~^~~~~~~~~~~
bitaro.cpp:22:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ind1 < v1.size()) {
      ~~~~~^~~~~~~~~~~
bitaro.cpp:23:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind2 < v2.size()) {
       ~~~~~^~~~~~~~~~~

Subtask 17 / 7

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 27 / 7

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 386 / 86

#	Verdict	Execution time	Memory	Grader output
Fetching results...