oj.uz

Submission #140188

# Submission time Handle Problem Language Result Execution time Memory
140188 2019-08-02T08:29:41 Z KLPP Minerals (JOI19_minerals) C++14
90 / 100
 536 ms 6724 KB 
#include "minerals.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int n;
set<int> s;
int last_answer;
void clear(){
  trav(a,s){
    Query(a);
  }
}
vector<pair<int,int> >Answers;
int Query2(int x){
  //cout<<x<<endl;
  last_answer=Query(x);
  if(s.find(x)==s.end()){
    s.insert(x);
  }else s.erase(x);
  return last_answer;
}
void Work(vector<int> v1,vector<int> v2){
  /*if(v1.size()!=0){
    int toggled=0;
    rep(i,0,v1.size()){
      if(s.find(v1[i])!=s.end())toggled++;
    }
    if(toggled!=v1.size() && toggled!=0)cout<<"ERR"<<endl;
  }*/
  /*rep(i,0,v1.size())cout<<v1[i]<<" ";
  cout<<endl;*/
  if(v1.size()==1){
    //cout<<v2.size()<<endl;
    Answers.push_back(pair<int,int>(v1[0],v2[0]));
    return;
  }
  vector<int> v11,v12,v21,v22;
  int mid=0;
  int toggled=0;
  rep(i,0,v1.size()){
    if(s.find(v1[i])!=s.end())toggled++;
  }
  if(toggled==0){
    mid=v1.size()/2;
  }else mid=(v1.size()+1)/2;
  rep(i,0,(int)v1.size()){
    if(i<mid){
      v11.push_back(v1[i]);
      if(s.find(v1[i])==s.end()){
	Query2(v1[i]);
      }
    }else{
      v12.push_back(v1[i]);
      if(s.find(v1[i])!=s.end()){
	Query2(v1[i]);
      }
    }
  }
  int LST=last_answer;
  random_shuffle(v2.begin(),v2.end());
  rep(i,0,(int)v2.size()){
    if(v21.size()==v11.size()){
      v22.push_back(v2[i]);
    }else{
      if(v22.size()==v12.size()){
	v21.push_back(v2[i]);
      }else{
	if(Query2(v2[i])==LST){
	  v21.push_back(v2[i]);
	}else{
	  v22.push_back(v2[i]);
	}
      }
    }
    LST=last_answer;
  }
  Work(v11,v21);
  Work(v12,v22);
}
void Solve(int N) {
  n=N;
  int Q=0;
  vector<int> v1,v2;
  last_answer=0;
  rep(i,1,2*n+1){
    if(Query2(i)==Q){
      //Query2(i);
      v2.push_back(i);
    }else{
      Q++;
      s.insert(i);
      v1.push_back(i);
    }
  }//cout<<Q<<endl;
  Work(v1,v2);
  rep(i,0,(int)Answers.size()){
    //cout<<Answers[i].first<<" "<<Answers[i].second<<endl;
    Answer(Answers[i].first,Answers[i].second);
  }
}

Compilation message

minerals.cpp: In function 'void Work(std::vector<int>, std::vector<int>)':
minerals.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
minerals.cpp:43:7:
   rep(i,0,v1.size()){
       ~~~~~~~~~~~~~              
minerals.cpp:43:3: note: in expansion of macro 'rep'
   rep(i,0,v1.size()){
   ^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 13 ms 504 KB Output is correct
3 Correct 28 ms 888 KB Output is correct
4 Correct 63 ms 1400 KB Output is correct
5 Correct 138 ms 2424 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 28 ms 888 KB Output is correct
8 Correct 63 ms 1400 KB Output is correct
9 Correct 138 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 90 ms 1836 KB Output is correct
12 Correct 147 ms 2552 KB Output is correct
13 Correct 137 ms 2556 KB Output is correct
14 Correct 123 ms 2348 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 28 ms 888 KB Output is correct
8 Correct 63 ms 1400 KB Output is correct
9 Correct 138 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 90 ms 1836 KB Output is correct
12 Correct 147 ms 2552 KB Output is correct
13 Correct 137 ms 2556 KB Output is correct
14 Correct 123 ms 2348 KB Output is correct
15 Correct 460 ms 5900 KB Output is correct
16 Correct 464 ms 6012 KB Output is correct
17 Correct 434 ms 6104 KB Output is correct
18 Correct 387 ms 5932 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 28 ms 888 KB Output is correct
8 Correct 63 ms 1400 KB Output is correct
9 Correct 138 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 90 ms 1836 KB Output is correct
12 Correct 147 ms 2552 KB Output is correct
13 Correct 137 ms 2556 KB Output is correct
14 Correct 123 ms 2348 KB Output is correct
15 Correct 460 ms 5900 KB Output is correct
16 Correct 464 ms 6012 KB Output is correct
17 Correct 434 ms 6104 KB Output is correct
18 Correct 387 ms 5932 KB Output is correct
19 Correct 480 ms 6260 KB Output is correct
20 Correct 490 ms 6132 KB Output is correct
21 Correct 441 ms 6256 KB Output is correct
22 Correct 399 ms 5876 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 28 ms 888 KB Output is correct
8 Correct 63 ms 1400 KB Output is correct
9 Correct 138 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 90 ms 1836 KB Output is correct
12 Correct 147 ms 2552 KB Output is correct
13 Correct 137 ms 2556 KB Output is correct
14 Correct 123 ms 2348 KB Output is correct
15 Correct 460 ms 5900 KB Output is correct
16 Correct 464 ms 6012 KB Output is correct
17 Correct 434 ms 6104 KB Output is correct
18 Correct 387 ms 5932 KB Output is correct
19 Correct 480 ms 6260 KB Output is correct
20 Correct 490 ms 6132 KB Output is correct
21 Correct 441 ms 6256 KB Output is correct
22 Correct 399 ms 5876 KB Output is correct
23 Correct 502 ms 6136 KB Output is correct
24 Correct 504 ms 6316 KB Output is correct
25 Correct 451 ms 6396 KB Output is correct
26 Correct 413 ms 6124 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 28 ms 888 KB Output is correct
8 Correct 63 ms 1400 KB Output is correct
9 Correct 138 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 90 ms 1836 KB Output is correct
12 Correct 147 ms 2552 KB Output is correct
13 Correct 137 ms 2556 KB Output is correct
14 Correct 123 ms 2348 KB Output is correct
15 Correct 460 ms 5900 KB Output is correct
16 Correct 464 ms 6012 KB Output is correct
17 Correct 434 ms 6104 KB Output is correct
18 Correct 387 ms 5932 KB Output is correct
19 Correct 480 ms 6260 KB Output is correct
20 Correct 490 ms 6132 KB Output is correct
21 Correct 441 ms 6256 KB Output is correct
22 Correct 399 ms 5876 KB Output is correct
23 Correct 502 ms 6136 KB Output is correct
24 Correct 504 ms 6316 KB Output is correct
25 Correct 451 ms 6396 KB Output is correct
26 Correct 413 ms 6124 KB Output is correct
27 Correct 516 ms 6336 KB Output is correct
28 Correct 514 ms 6260 KB Output is correct
29 Correct 465 ms 6604 KB Output is correct
30 Correct 424 ms 6172 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 28 ms 888 KB Output is correct
8 Correct 63 ms 1400 KB Output is correct
9 Correct 138 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 90 ms 1836 KB Output is correct
12 Correct 147 ms 2552 KB Output is correct
13 Correct 137 ms 2556 KB Output is correct
14 Correct 123 ms 2348 KB Output is correct
15 Correct 460 ms 5900 KB Output is correct
16 Correct 464 ms 6012 KB Output is correct
17 Correct 434 ms 6104 KB Output is correct
18 Correct 387 ms 5932 KB Output is correct
19 Correct 480 ms 6260 KB Output is correct
20 Correct 490 ms 6132 KB Output is correct
21 Correct 441 ms 6256 KB Output is correct
22 Correct 399 ms 5876 KB Output is correct
23 Correct 502 ms 6136 KB Output is correct
24 Correct 504 ms 6316 KB Output is correct
25 Correct 451 ms 6396 KB Output is correct
26 Correct 413 ms 6124 KB Output is correct
27 Correct 516 ms 6336 KB Output is correct
28 Correct 514 ms 6260 KB Output is correct
29 Correct 465 ms 6604 KB Output is correct
30 Correct 424 ms 6172 KB Output is correct
31 Correct 536 ms 6564 KB Output is correct
32 Correct 528 ms 6516 KB Output is correct
33 Correct 485 ms 6724 KB Output is correct
34 Correct 434 ms 6416 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 28 ms 888 KB Output is correct
8 Correct 63 ms 1400 KB Output is correct
9 Correct 138 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 90 ms 1836 KB Output is correct
12 Correct 147 ms 2552 KB Output is correct
13 Correct 137 ms 2556 KB Output is correct
14 Correct 123 ms 2348 KB Output is correct
15 Correct 460 ms 5900 KB Output is correct
16 Correct 464 ms 6012 KB Output is correct
17 Correct 434 ms 6104 KB Output is correct
18 Correct 387 ms 5932 KB Output is correct
19 Correct 480 ms 6260 KB Output is correct
20 Correct 490 ms 6132 KB Output is correct
21 Correct 441 ms 6256 KB Output is correct
22 Correct 399 ms 5876 KB Output is correct
23 Correct 502 ms 6136 KB Output is correct
24 Correct 504 ms 6316 KB Output is correct
25 Correct 451 ms 6396 KB Output is correct
26 Correct 413 ms 6124 KB Output is correct
27 Correct 516 ms 6336 KB Output is correct
28 Correct 514 ms 6260 KB Output is correct
29 Correct 465 ms 6604 KB Output is correct
30 Correct 424 ms 6172 KB Output is correct
31 Correct 536 ms 6564 KB Output is correct
32 Correct 528 ms 6516 KB Output is correct
33 Correct 485 ms 6724 KB Output is correct
34 Correct 434 ms 6416 KB Output is correct
35 Incorrect 534 ms 6576 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -