oj.uz

Submission #140191

# Submission time Handle Problem Language Result Execution time Memory
140191 2019-08-02T08:36:22 Z KLPP Minerals (JOI19_minerals) C++14
90 / 100
 613 ms 6512 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;
}
int ABS(int x){
  if(x>0)return x;
  return -x;
}
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;
  }
  int TOGGLE1=0;
  int TOGGLE2=0;
  rep(i,0,v1.size()){
    if(s.find(v1[i])!=s.end())TOGGLE1++;
  }
  rep(i,0,v2.size()){
    if(s.find(v2[i])!=s.end())TOGGLE2++;
  }
  if(ABS(TOGGLE2*2-v2.size())<ABS(TOGGLE1*2-v1.size())){
    swap(v1,v2);
  }
  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) {
  srand(1007);
  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:46:7:
   rep(i,0,v1.size()){
       ~~~~~~~~~~~~~              
minerals.cpp:46:3: note: in expansion of macro 'rep'
   rep(i,0,v1.size()){
   ^~~
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:49:7:
   rep(i,0,v2.size()){
       ~~~~~~~~~~~~~              
minerals.cpp:49:3: note: in expansion of macro 'rep'
   rep(i,0,v2.size()){
   ^~~
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:58:7:
   rep(i,0,v1.size()){
       ~~~~~~~~~~~~~              
minerals.cpp:58: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 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 16 ms 632 KB Output is correct
3 Correct 32 ms 864 KB Output is correct
4 Correct 72 ms 1400 KB Output is correct
5 Correct 150 ms 2348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 32 ms 864 KB Output is correct
8 Correct 72 ms 1400 KB Output is correct
9 Correct 150 ms 2348 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 100 ms 1760 KB Output is correct
12 Correct 159 ms 2440 KB Output is correct
13 Correct 114 ms 2636 KB Output is correct
14 Correct 99 ms 2352 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 32 ms 864 KB Output is correct
8 Correct 72 ms 1400 KB Output is correct
9 Correct 150 ms 2348 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 100 ms 1760 KB Output is correct
12 Correct 159 ms 2440 KB Output is correct
13 Correct 114 ms 2636 KB Output is correct
14 Correct 99 ms 2352 KB Output is correct
15 Correct 522 ms 5964 KB Output is correct
16 Correct 550 ms 6052 KB Output is correct
17 Correct 337 ms 6048 KB Output is correct
18 Correct 298 ms 5748 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 32 ms 864 KB Output is correct
8 Correct 72 ms 1400 KB Output is correct
9 Correct 150 ms 2348 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 100 ms 1760 KB Output is correct
12 Correct 159 ms 2440 KB Output is correct
13 Correct 114 ms 2636 KB Output is correct
14 Correct 99 ms 2352 KB Output is correct
15 Correct 522 ms 5964 KB Output is correct
16 Correct 550 ms 6052 KB Output is correct
17 Correct 337 ms 6048 KB Output is correct
18 Correct 298 ms 5748 KB Output is correct
19 Correct 543 ms 6348 KB Output is correct
20 Correct 551 ms 6116 KB Output is correct
21 Correct 357 ms 6256 KB Output is correct
22 Correct 304 ms 5880 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 32 ms 864 KB Output is correct
8 Correct 72 ms 1400 KB Output is correct
9 Correct 150 ms 2348 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 100 ms 1760 KB Output is correct
12 Correct 159 ms 2440 KB Output is correct
13 Correct 114 ms 2636 KB Output is correct
14 Correct 99 ms 2352 KB Output is correct
15 Correct 522 ms 5964 KB Output is correct
16 Correct 550 ms 6052 KB Output is correct
17 Correct 337 ms 6048 KB Output is correct
18 Correct 298 ms 5748 KB Output is correct
19 Correct 543 ms 6348 KB Output is correct
20 Correct 551 ms 6116 KB Output is correct
21 Correct 357 ms 6256 KB Output is correct
22 Correct 304 ms 5880 KB Output is correct
23 Correct 546 ms 6004 KB Output is correct
24 Correct 558 ms 6036 KB Output is correct
25 Correct 378 ms 6304 KB Output is correct
26 Correct 310 ms 6052 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 32 ms 864 KB Output is correct
8 Correct 72 ms 1400 KB Output is correct
9 Correct 150 ms 2348 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 100 ms 1760 KB Output is correct
12 Correct 159 ms 2440 KB Output is correct
13 Correct 114 ms 2636 KB Output is correct
14 Correct 99 ms 2352 KB Output is correct
15 Correct 522 ms 5964 KB Output is correct
16 Correct 550 ms 6052 KB Output is correct
17 Correct 337 ms 6048 KB Output is correct
18 Correct 298 ms 5748 KB Output is correct
19 Correct 543 ms 6348 KB Output is correct
20 Correct 551 ms 6116 KB Output is correct
21 Correct 357 ms 6256 KB Output is correct
22 Correct 304 ms 5880 KB Output is correct
23 Correct 546 ms 6004 KB Output is correct
24 Correct 558 ms 6036 KB Output is correct
25 Correct 378 ms 6304 KB Output is correct
26 Correct 310 ms 6052 KB Output is correct
27 Correct 540 ms 6028 KB Output is correct
28 Correct 566 ms 6200 KB Output is correct
29 Correct 383 ms 6412 KB Output is correct
30 Correct 321 ms 5872 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 32 ms 864 KB Output is correct
8 Correct 72 ms 1400 KB Output is correct
9 Correct 150 ms 2348 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 100 ms 1760 KB Output is correct
12 Correct 159 ms 2440 KB Output is correct
13 Correct 114 ms 2636 KB Output is correct
14 Correct 99 ms 2352 KB Output is correct
15 Correct 522 ms 5964 KB Output is correct
16 Correct 550 ms 6052 KB Output is correct
17 Correct 337 ms 6048 KB Output is correct
18 Correct 298 ms 5748 KB Output is correct
19 Correct 543 ms 6348 KB Output is correct
20 Correct 551 ms 6116 KB Output is correct
21 Correct 357 ms 6256 KB Output is correct
22 Correct 304 ms 5880 KB Output is correct
23 Correct 546 ms 6004 KB Output is correct
24 Correct 558 ms 6036 KB Output is correct
25 Correct 378 ms 6304 KB Output is correct
26 Correct 310 ms 6052 KB Output is correct
27 Correct 540 ms 6028 KB Output is correct
28 Correct 566 ms 6200 KB Output is correct
29 Correct 383 ms 6412 KB Output is correct
30 Correct 321 ms 5872 KB Output is correct
31 Correct 583 ms 6336 KB Output is correct
32 Correct 613 ms 6260 KB Output is correct
33 Correct 394 ms 6512 KB Output is correct
34 Correct 336 ms 5924 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 32 ms 864 KB Output is correct
8 Correct 72 ms 1400 KB Output is correct
9 Correct 150 ms 2348 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 100 ms 1760 KB Output is correct
12 Correct 159 ms 2440 KB Output is correct
13 Correct 114 ms 2636 KB Output is correct
14 Correct 99 ms 2352 KB Output is correct
15 Correct 522 ms 5964 KB Output is correct
16 Correct 550 ms 6052 KB Output is correct
17 Correct 337 ms 6048 KB Output is correct
18 Correct 298 ms 5748 KB Output is correct
19 Correct 543 ms 6348 KB Output is correct
20 Correct 551 ms 6116 KB Output is correct
21 Correct 357 ms 6256 KB Output is correct
22 Correct 304 ms 5880 KB Output is correct
23 Correct 546 ms 6004 KB Output is correct
24 Correct 558 ms 6036 KB Output is correct
25 Correct 378 ms 6304 KB Output is correct
26 Correct 310 ms 6052 KB Output is correct
27 Correct 540 ms 6028 KB Output is correct
28 Correct 566 ms 6200 KB Output is correct
29 Correct 383 ms 6412 KB Output is correct
30 Correct 321 ms 5872 KB Output is correct
31 Correct 583 ms 6336 KB Output is correct
32 Correct 613 ms 6260 KB Output is correct
33 Correct 394 ms 6512 KB Output is correct
34 Correct 336 ms 5924 KB Output is correct
35 Incorrect 587 ms 6364 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -