oj.uz

Submission #950621

# Submission time Handle Problem Language Result Execution time Memory
950621 2024-03-20T13:56:30 Z pcc Minerals (JOI19_minerals) C++17
6 / 100
 92 ms 1868 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);
	mt19937 seed(time(NULL));
	shuffle(vv.begin(),vv.end(),seed);

	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;
	bool dir = false;
	for(int i = 0;i<B;i++){
		int cnt = 0;
		if(req[i].empty())continue;
		vector<int> turn;
		for(int j = 0;j<req[i].size();j++)turn.push_back(j);
		sort(turn.begin(),turn.end(),[&](int a,int b){return dir?req[i][a].fs<req[i][b].fs:req[i][a].fs>req[i][b].fs;});
		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(auto j:turn){
			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-l)*0.37;
			bk[i+1].push_back({});
			bk[i+1].push_back({});
			while(pr<mid){
				pre = Query(v[0][++pr]);
			}
			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;
				}
				if(bk[i+1].end()[-2].size() == mid-l+1){
					bk[i+1].end()[-1].push_back(m);
					continue;
				}
				if(bk[i+1].end()[-1].size() == r-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);
			}
		}
		dir ^= 1;
	}
	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:49: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]
   49 |   for(int j = 0;j<req[i].size();j++)turn.push_back(j);
      |                 ~^~~~~~~~~~~~~~
minerals.cpp:52:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   52 |   for(auto &j:req[i])cerr<<j.fs<<' '<<j.sc<<',';cerr<<endl;
      |   ^~~
minerals.cpp:52:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   52 |   for(auto &j:req[i])cerr<<j.fs<<' '<<j.sc<<',';cerr<<endl;
      |                                                 ^~~~
minerals.cpp:78:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |     if(bk[i+1].end()[-2].size() == mid-l+1){
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
minerals.cpp:82:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} [-Wsign-compare]
   82 |     if(bk[i+1].end()[-1].size() == r-mid){
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
minerals.cpp:46:7: warning: unused variable 'cnt' [-Wunused-variable]
   46 |   int cnt = 0;
      |       ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 480 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 512 KB Output is correct
2 Runtime error 92 ms 1868 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 43 ms 512 KB Output is correct
6 Runtime error 92 ms 1868 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 43 ms 512 KB Output is correct
6 Runtime error 92 ms 1868 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 43 ms 512 KB Output is correct
6 Runtime error 92 ms 1868 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 43 ms 512 KB Output is correct
6 Runtime error 92 ms 1868 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 43 ms 512 KB Output is correct
6 Runtime error 92 ms 1868 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 43 ms 512 KB Output is correct
6 Runtime error 92 ms 1868 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 43 ms 512 KB Output is correct
6 Runtime error 92 ms 1868 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -