oj.uz

답안 #950625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950625 2024-03-20T13:57:19 Z pcc Minerals (JOI19_minerals) C++17
40 / 100
 832 ms 6328 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.5;
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 576 KB Output is correct
2 Correct 86 ms 940 KB Output is correct
3 Correct 181 ms 1612 KB Output is correct
4 Correct 384 ms 3308 KB Output is correct
5 Correct 776 ms 5920 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 86 ms 940 KB Output is correct
7 Correct 181 ms 1612 KB Output is correct
8 Correct 384 ms 3308 KB Output is correct
9 Correct 776 ms 5920 KB Output is correct
10 Correct 44 ms 592 KB Output is correct
11 Correct 489 ms 4220 KB Output is correct
12 Correct 760 ms 5948 KB Output is correct
13 Correct 788 ms 5896 KB Output is correct
14 Correct 808 ms 5852 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 86 ms 940 KB Output is correct
7 Correct 181 ms 1612 KB Output is correct
8 Correct 384 ms 3308 KB Output is correct
9 Correct 776 ms 5920 KB Output is correct
10 Correct 44 ms 592 KB Output is correct
11 Correct 489 ms 4220 KB Output is correct
12 Correct 760 ms 5948 KB Output is correct
13 Correct 788 ms 5896 KB Output is correct
14 Correct 808 ms 5852 KB Output is correct
15 Incorrect 832 ms 6328 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 86 ms 940 KB Output is correct
7 Correct 181 ms 1612 KB Output is correct
8 Correct 384 ms 3308 KB Output is correct
9 Correct 776 ms 5920 KB Output is correct
10 Correct 44 ms 592 KB Output is correct
11 Correct 489 ms 4220 KB Output is correct
12 Correct 760 ms 5948 KB Output is correct
13 Correct 788 ms 5896 KB Output is correct
14 Correct 808 ms 5852 KB Output is correct
15 Incorrect 832 ms 6328 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 86 ms 940 KB Output is correct
7 Correct 181 ms 1612 KB Output is correct
8 Correct 384 ms 3308 KB Output is correct
9 Correct 776 ms 5920 KB Output is correct
10 Correct 44 ms 592 KB Output is correct
11 Correct 489 ms 4220 KB Output is correct
12 Correct 760 ms 5948 KB Output is correct
13 Correct 788 ms 5896 KB Output is correct
14 Correct 808 ms 5852 KB Output is correct
15 Incorrect 832 ms 6328 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 86 ms 940 KB Output is correct
7 Correct 181 ms 1612 KB Output is correct
8 Correct 384 ms 3308 KB Output is correct
9 Correct 776 ms 5920 KB Output is correct
10 Correct 44 ms 592 KB Output is correct
11 Correct 489 ms 4220 KB Output is correct
12 Correct 760 ms 5948 KB Output is correct
13 Correct 788 ms 5896 KB Output is correct
14 Correct 808 ms 5852 KB Output is correct
15 Incorrect 832 ms 6328 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 86 ms 940 KB Output is correct
7 Correct 181 ms 1612 KB Output is correct
8 Correct 384 ms 3308 KB Output is correct
9 Correct 776 ms 5920 KB Output is correct
10 Correct 44 ms 592 KB Output is correct
11 Correct 489 ms 4220 KB Output is correct
12 Correct 760 ms 5948 KB Output is correct
13 Correct 788 ms 5896 KB Output is correct
14 Correct 808 ms 5852 KB Output is correct
15 Incorrect 832 ms 6328 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 42 ms 576 KB Output is correct
6 Correct 86 ms 940 KB Output is correct
7 Correct 181 ms 1612 KB Output is correct
8 Correct 384 ms 3308 KB Output is correct
9 Correct 776 ms 5920 KB Output is correct
10 Correct 44 ms 592 KB Output is correct
11 Correct 489 ms 4220 KB Output is correct
12 Correct 760 ms 5948 KB Output is correct
13 Correct 788 ms 5896 KB Output is correct
14 Correct 808 ms 5852 KB Output is correct
15 Incorrect 832 ms 6328 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -