oj.uz

Submission #140186

# Submission time Handle Problem Language Result Execution time Memory
140186 2019-08-02T08:28:44 Z KLPP Minerals (JOI19_minerals) C++14
90 / 100
 468 ms 6560 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;
  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 376 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 12 ms 504 KB Output is correct
3 Correct 25 ms 888 KB Output is correct
4 Correct 53 ms 1400 KB Output is correct
5 Correct 116 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 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 25 ms 888 KB Output is correct
8 Correct 53 ms 1400 KB Output is correct
9 Correct 116 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 76 ms 1804 KB Output is correct
12 Correct 128 ms 2440 KB Output is correct
13 Correct 90 ms 2620 KB Output is correct
14 Correct 78 ms 2424 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 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 25 ms 888 KB Output is correct
8 Correct 53 ms 1400 KB Output is correct
9 Correct 116 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 76 ms 1804 KB Output is correct
12 Correct 128 ms 2440 KB Output is correct
13 Correct 90 ms 2620 KB Output is correct
14 Correct 78 ms 2424 KB Output is correct
15 Correct 380 ms 5956 KB Output is correct
16 Correct 374 ms 5644 KB Output is correct
17 Correct 278 ms 6000 KB Output is correct
18 Correct 237 ms 5920 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 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 25 ms 888 KB Output is correct
8 Correct 53 ms 1400 KB Output is correct
9 Correct 116 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 76 ms 1804 KB Output is correct
12 Correct 128 ms 2440 KB Output is correct
13 Correct 90 ms 2620 KB Output is correct
14 Correct 78 ms 2424 KB Output is correct
15 Correct 380 ms 5956 KB Output is correct
16 Correct 374 ms 5644 KB Output is correct
17 Correct 278 ms 6000 KB Output is correct
18 Correct 237 ms 5920 KB Output is correct
19 Correct 387 ms 5760 KB Output is correct
20 Correct 403 ms 5876 KB Output is correct
21 Correct 282 ms 6216 KB Output is correct
22 Correct 242 ms 5892 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 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 25 ms 888 KB Output is correct
8 Correct 53 ms 1400 KB Output is correct
9 Correct 116 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 76 ms 1804 KB Output is correct
12 Correct 128 ms 2440 KB Output is correct
13 Correct 90 ms 2620 KB Output is correct
14 Correct 78 ms 2424 KB Output is correct
15 Correct 380 ms 5956 KB Output is correct
16 Correct 374 ms 5644 KB Output is correct
17 Correct 278 ms 6000 KB Output is correct
18 Correct 237 ms 5920 KB Output is correct
19 Correct 387 ms 5760 KB Output is correct
20 Correct 403 ms 5876 KB Output is correct
21 Correct 282 ms 6216 KB Output is correct
22 Correct 242 ms 5892 KB Output is correct
23 Correct 405 ms 6052 KB Output is correct
24 Correct 412 ms 5908 KB Output is correct
25 Correct 295 ms 6252 KB Output is correct
26 Correct 247 ms 5984 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 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 25 ms 888 KB Output is correct
8 Correct 53 ms 1400 KB Output is correct
9 Correct 116 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 76 ms 1804 KB Output is correct
12 Correct 128 ms 2440 KB Output is correct
13 Correct 90 ms 2620 KB Output is correct
14 Correct 78 ms 2424 KB Output is correct
15 Correct 380 ms 5956 KB Output is correct
16 Correct 374 ms 5644 KB Output is correct
17 Correct 278 ms 6000 KB Output is correct
18 Correct 237 ms 5920 KB Output is correct
19 Correct 387 ms 5760 KB Output is correct
20 Correct 403 ms 5876 KB Output is correct
21 Correct 282 ms 6216 KB Output is correct
22 Correct 242 ms 5892 KB Output is correct
23 Correct 405 ms 6052 KB Output is correct
24 Correct 412 ms 5908 KB Output is correct
25 Correct 295 ms 6252 KB Output is correct
26 Correct 247 ms 5984 KB Output is correct
27 Correct 416 ms 6100 KB Output is correct
28 Correct 415 ms 6132 KB Output is correct
29 Correct 305 ms 6528 KB Output is correct
30 Correct 253 ms 5796 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 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 25 ms 888 KB Output is correct
8 Correct 53 ms 1400 KB Output is correct
9 Correct 116 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 76 ms 1804 KB Output is correct
12 Correct 128 ms 2440 KB Output is correct
13 Correct 90 ms 2620 KB Output is correct
14 Correct 78 ms 2424 KB Output is correct
15 Correct 380 ms 5956 KB Output is correct
16 Correct 374 ms 5644 KB Output is correct
17 Correct 278 ms 6000 KB Output is correct
18 Correct 237 ms 5920 KB Output is correct
19 Correct 387 ms 5760 KB Output is correct
20 Correct 403 ms 5876 KB Output is correct
21 Correct 282 ms 6216 KB Output is correct
22 Correct 242 ms 5892 KB Output is correct
23 Correct 405 ms 6052 KB Output is correct
24 Correct 412 ms 5908 KB Output is correct
25 Correct 295 ms 6252 KB Output is correct
26 Correct 247 ms 5984 KB Output is correct
27 Correct 416 ms 6100 KB Output is correct
28 Correct 415 ms 6132 KB Output is correct
29 Correct 305 ms 6528 KB Output is correct
30 Correct 253 ms 5796 KB Output is correct
31 Correct 468 ms 6340 KB Output is correct
32 Correct 430 ms 6244 KB Output is correct
33 Correct 310 ms 6560 KB Output is correct
34 Correct 264 ms 6004 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 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 25 ms 888 KB Output is correct
8 Correct 53 ms 1400 KB Output is correct
9 Correct 116 ms 2424 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 76 ms 1804 KB Output is correct
12 Correct 128 ms 2440 KB Output is correct
13 Correct 90 ms 2620 KB Output is correct
14 Correct 78 ms 2424 KB Output is correct
15 Correct 380 ms 5956 KB Output is correct
16 Correct 374 ms 5644 KB Output is correct
17 Correct 278 ms 6000 KB Output is correct
18 Correct 237 ms 5920 KB Output is correct
19 Correct 387 ms 5760 KB Output is correct
20 Correct 403 ms 5876 KB Output is correct
21 Correct 282 ms 6216 KB Output is correct
22 Correct 242 ms 5892 KB Output is correct
23 Correct 405 ms 6052 KB Output is correct
24 Correct 412 ms 5908 KB Output is correct
25 Correct 295 ms 6252 KB Output is correct
26 Correct 247 ms 5984 KB Output is correct
27 Correct 416 ms 6100 KB Output is correct
28 Correct 415 ms 6132 KB Output is correct
29 Correct 305 ms 6528 KB Output is correct
30 Correct 253 ms 5796 KB Output is correct
31 Correct 468 ms 6340 KB Output is correct
32 Correct 430 ms 6244 KB Output is correct
33 Correct 310 ms 6560 KB Output is correct
34 Correct 264 ms 6004 KB Output is correct
35 Incorrect 439 ms 6356 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -