oj.uz

답안 #950617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950617 2024-03-20T13:53:46 Z pcc Minerals (JOI19_minerals) C++17
40 / 100
 767 ms 6064 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)>>1;
			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);
			}
		}
	}
	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 472 KB Output is correct
4 Correct 4 ms 464 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 600 KB Output is correct
2 Correct 87 ms 1024 KB Output is correct
3 Correct 181 ms 1616 KB Output is correct
4 Correct 383 ms 3300 KB Output is correct
5 Correct 762 ms 6064 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 472 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 44 ms 600 KB Output is correct
6 Correct 87 ms 1024 KB Output is correct
7 Correct 181 ms 1616 KB Output is correct
8 Correct 383 ms 3300 KB Output is correct
9 Correct 762 ms 6064 KB Output is correct
10 Correct 44 ms 600 KB Output is correct
11 Correct 488 ms 4172 KB Output is correct
12 Correct 754 ms 5796 KB Output is correct
13 Correct 767 ms 5756 KB Output is correct
14 Correct 751 ms 5716 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 472 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 44 ms 600 KB Output is correct
6 Correct 87 ms 1024 KB Output is correct
7 Correct 181 ms 1616 KB Output is correct
8 Correct 383 ms 3300 KB Output is correct
9 Correct 762 ms 6064 KB Output is correct
10 Correct 44 ms 600 KB Output is correct
11 Correct 488 ms 4172 KB Output is correct
12 Correct 754 ms 5796 KB Output is correct
13 Correct 767 ms 5756 KB Output is correct
14 Correct 751 ms 5716 KB Output is correct
15 Incorrect 592 ms 5564 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 472 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 44 ms 600 KB Output is correct
6 Correct 87 ms 1024 KB Output is correct
7 Correct 181 ms 1616 KB Output is correct
8 Correct 383 ms 3300 KB Output is correct
9 Correct 762 ms 6064 KB Output is correct
10 Correct 44 ms 600 KB Output is correct
11 Correct 488 ms 4172 KB Output is correct
12 Correct 754 ms 5796 KB Output is correct
13 Correct 767 ms 5756 KB Output is correct
14 Correct 751 ms 5716 KB Output is correct
15 Incorrect 592 ms 5564 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 472 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 44 ms 600 KB Output is correct
6 Correct 87 ms 1024 KB Output is correct
7 Correct 181 ms 1616 KB Output is correct
8 Correct 383 ms 3300 KB Output is correct
9 Correct 762 ms 6064 KB Output is correct
10 Correct 44 ms 600 KB Output is correct
11 Correct 488 ms 4172 KB Output is correct
12 Correct 754 ms 5796 KB Output is correct
13 Correct 767 ms 5756 KB Output is correct
14 Correct 751 ms 5716 KB Output is correct
15 Incorrect 592 ms 5564 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 472 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 44 ms 600 KB Output is correct
6 Correct 87 ms 1024 KB Output is correct
7 Correct 181 ms 1616 KB Output is correct
8 Correct 383 ms 3300 KB Output is correct
9 Correct 762 ms 6064 KB Output is correct
10 Correct 44 ms 600 KB Output is correct
11 Correct 488 ms 4172 KB Output is correct
12 Correct 754 ms 5796 KB Output is correct
13 Correct 767 ms 5756 KB Output is correct
14 Correct 751 ms 5716 KB Output is correct
15 Incorrect 592 ms 5564 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 472 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 44 ms 600 KB Output is correct
6 Correct 87 ms 1024 KB Output is correct
7 Correct 181 ms 1616 KB Output is correct
8 Correct 383 ms 3300 KB Output is correct
9 Correct 762 ms 6064 KB Output is correct
10 Correct 44 ms 600 KB Output is correct
11 Correct 488 ms 4172 KB Output is correct
12 Correct 754 ms 5796 KB Output is correct
13 Correct 767 ms 5756 KB Output is correct
14 Correct 751 ms 5716 KB Output is correct
15 Incorrect 592 ms 5564 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 472 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 44 ms 600 KB Output is correct
6 Correct 87 ms 1024 KB Output is correct
7 Correct 181 ms 1616 KB Output is correct
8 Correct 383 ms 3300 KB Output is correct
9 Correct 762 ms 6064 KB Output is correct
10 Correct 44 ms 600 KB Output is correct
11 Correct 488 ms 4172 KB Output is correct
12 Correct 754 ms 5796 KB Output is correct
13 Correct 767 ms 5756 KB Output is correct
14 Correct 751 ms 5716 KB Output is correct
15 Incorrect 592 ms 5564 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -