oj.uz

Submission #950605

# Submission time Handle Problem Language Result Execution time Memory
950605 2024-03-20T13:38:19 Z pcc Minerals (JOI19_minerals) C++17
40 / 100
 807 ms 5872 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

/*
int v = Query(1);
Answer(i, 2 * N + 1 - i);
*/

#define pii pair<int,int>
#define fs first
#define sc second
const int B = 15;
const int mxn = 86011;
vector<pii> req[B];
vector<int> v[2];
int pl,pr;
vector<vector<int>> bk[B];
vector<pii> ans;
int before[mxn];

void Solve(int N) {
	vector<int> vv;
	for(int i = 1;i<=N*2;i++)vv.push_back(i);
	srand(time(NULL));
	random_shuffle(vv.begin(),vv.end());

	int pre = 0;
	for(auto &i:vv){
		int tmp = Query(i);
		if(tmp==pre){
			v[1].push_back(i);
			pre = Query(i);
		}
		else pre = tmp,v[0].push_back(i);
		before[i] = pre;
	}
	assert(v[0].size() == v[1].size());
	req[0].push_back(pii(0,N-1));
	bk[0].push_back({});
	for(int i = 0;i<v[1].size();i++)bk[0].back().push_back(v[1][i]);

	pl = 0,pr = v[0].size()-1;
	for(int i = 0;i<B;i++){
		int cnt = 0;
		if(req[i].empty())continue;
		while(pl>0){
			pre = Query(v[0][--pl]);
		}
		while(pr>0){
			pre = Query(v[0][pr--]);
		}
		cerr<<i<<endl;
		for(auto &j:req[i])cerr<<j.fs<<' '<<j.sc<<',';cerr<<endl;
		for(auto &j:bk[i]){for(auto &l:j)cerr<<l<<' ';cerr<<",";}cerr<<endl;
		assert(req[i].size() == bk[i].size());
		for(int j = 0;j<req[i].size();j++){
			auto [l,r] = req[i][j];
			if(l == r){
				ans.push_back(pii(bk[i][j][0],v[0][l]));
				continue;
			}
			int mid = (l+r)>>1;
			bk[i+1].push_back({});
			bk[i+1].push_back({});
			while(pr<mid){
				pre = Query(v[0][++pr]);
			}
			cerr<<pl<<','<<pr<<":"<<pre<<endl;
			req[i+1].push_back(pii(l,mid));
			req[i+1].push_back(pii(mid+1,r));
			for(auto &m:bk[i][j]){
				if(before[m]<=before[v[0][mid]]){
					bk[i+1].end()[-2].push_back(m);
					continue;
				}
				auto tmp = Query(m);
				if(pre == tmp)bk[i+1].end()[-2].push_back(m);
				else bk[i+1].end()[-1].push_back(m);
				pre = Query(m);
			}
		}
	}
	for(auto &i:ans)Answer(i.fs,i.sc);
	return;
}

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0;i<v[1].size();i++)bk[0].back().push_back(v[1][i]);
      |                ~^~~~~~~~~~~~
minerals.cpp:54:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |   for(auto &j:req[i])cerr<<j.fs<<' '<<j.sc<<',';cerr<<endl;
      |   ^~~
minerals.cpp:54:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   54 |   for(auto &j:req[i])cerr<<j.fs<<' '<<j.sc<<',';cerr<<endl;
      |                                                 ^~~~
minerals.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j = 0;j<req[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
minerals.cpp:45:7: warning: unused variable 'cnt' [-Wunused-variable]
   45 |   int cnt = 0;
      |       ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 712 KB Output is correct
2 Correct 96 ms 984 KB Output is correct
3 Correct 187 ms 1620 KB Output is correct
4 Correct 419 ms 2932 KB Output is correct
5 Correct 794 ms 5736 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 46 ms 712 KB Output is correct
6 Correct 96 ms 984 KB Output is correct
7 Correct 187 ms 1620 KB Output is correct
8 Correct 419 ms 2932 KB Output is correct
9 Correct 794 ms 5736 KB Output is correct
10 Correct 45 ms 704 KB Output is correct
11 Correct 533 ms 4096 KB Output is correct
12 Correct 807 ms 5716 KB Output is correct
13 Correct 783 ms 5872 KB Output is correct
14 Correct 804 ms 5764 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 46 ms 712 KB Output is correct
6 Correct 96 ms 984 KB Output is correct
7 Correct 187 ms 1620 KB Output is correct
8 Correct 419 ms 2932 KB Output is correct
9 Correct 794 ms 5736 KB Output is correct
10 Correct 45 ms 704 KB Output is correct
11 Correct 533 ms 4096 KB Output is correct
12 Correct 807 ms 5716 KB Output is correct
13 Correct 783 ms 5872 KB Output is correct
14 Correct 804 ms 5764 KB Output is correct
15 Incorrect 615 ms 5188 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 46 ms 712 KB Output is correct
6 Correct 96 ms 984 KB Output is correct
7 Correct 187 ms 1620 KB Output is correct
8 Correct 419 ms 2932 KB Output is correct
9 Correct 794 ms 5736 KB Output is correct
10 Correct 45 ms 704 KB Output is correct
11 Correct 533 ms 4096 KB Output is correct
12 Correct 807 ms 5716 KB Output is correct
13 Correct 783 ms 5872 KB Output is correct
14 Correct 804 ms 5764 KB Output is correct
15 Incorrect 615 ms 5188 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 46 ms 712 KB Output is correct
6 Correct 96 ms 984 KB Output is correct
7 Correct 187 ms 1620 KB Output is correct
8 Correct 419 ms 2932 KB Output is correct
9 Correct 794 ms 5736 KB Output is correct
10 Correct 45 ms 704 KB Output is correct
11 Correct 533 ms 4096 KB Output is correct
12 Correct 807 ms 5716 KB Output is correct
13 Correct 783 ms 5872 KB Output is correct
14 Correct 804 ms 5764 KB Output is correct
15 Incorrect 615 ms 5188 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 46 ms 712 KB Output is correct
6 Correct 96 ms 984 KB Output is correct
7 Correct 187 ms 1620 KB Output is correct
8 Correct 419 ms 2932 KB Output is correct
9 Correct 794 ms 5736 KB Output is correct
10 Correct 45 ms 704 KB Output is correct
11 Correct 533 ms 4096 KB Output is correct
12 Correct 807 ms 5716 KB Output is correct
13 Correct 783 ms 5872 KB Output is correct
14 Correct 804 ms 5764 KB Output is correct
15 Incorrect 615 ms 5188 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 46 ms 712 KB Output is correct
6 Correct 96 ms 984 KB Output is correct
7 Correct 187 ms 1620 KB Output is correct
8 Correct 419 ms 2932 KB Output is correct
9 Correct 794 ms 5736 KB Output is correct
10 Correct 45 ms 704 KB Output is correct
11 Correct 533 ms 4096 KB Output is correct
12 Correct 807 ms 5716 KB Output is correct
13 Correct 783 ms 5872 KB Output is correct
14 Correct 804 ms 5764 KB Output is correct
15 Incorrect 615 ms 5188 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 46 ms 712 KB Output is correct
6 Correct 96 ms 984 KB Output is correct
7 Correct 187 ms 1620 KB Output is correct
8 Correct 419 ms 2932 KB Output is correct
9 Correct 794 ms 5736 KB Output is correct
10 Correct 45 ms 704 KB Output is correct
11 Correct 533 ms 4096 KB Output is correct
12 Correct 807 ms 5716 KB Output is correct
13 Correct 783 ms 5872 KB Output is correct
14 Correct 804 ms 5764 KB Output is correct
15 Incorrect 615 ms 5188 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -