oj.uz

답안 #530324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530324 2022-02-25T04:50:04 Z fhvirus Minerals (JOI19_minerals) C++17
85 / 100
 441 ms 6448 KB 
#include "minerals.h"

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#define debug(...) ((void)0)
#endif

void solve(vector<int> &a, vector<int> &b, bool in){
	debug("solving:", a, b);
	assert(a.size() == b.size());
	int n = a.size();

	if(n < 1) return;
	if(n == 1){
		Answer(a[0], b[0]);
		return;
	}

	vector<int> la, lb, ra, rb;
	int h = ceil(a.size() * 0.38);
	for(int i = 0; i < h; ++i) la.pb(a[i]);
	for(int i = h; i < a.size(); ++i) lb.pb(a[i]);

	int ls, cs;
	for(int i: la) cs = Query(i);

	random_device rd;
	mt19937 mt(rd());
	shuffle(AI(b), mt);
	for(int i: b){
		ls = cs;
		cs = Query(i);
		if(cs == ls ^ in) ra.pb(i);
		else rb.pb(i);
	}

	debug(la, lb);
	debug(ra, rb);

	solve(la, ra, !in);
	solve(lb, rb,  in);
}

void Solve(int N) {
	vector<int> hulan;
	for(int i = 1; i <= N * 2; ++i) hulan.pb(i);

	vector<vector<int>> as, bs;
	vector<int> a, b;
	int ls = 0, cs;
	for(int i: hulan){
		cs = Query(i);
		if(cs == ls) b.pb(i);
		else a.pb(i);

		if(a.size() == b.size()){
			as.pb(a);
			bs.pb(b);
			a.clear();
			b.clear();
		}

		ls = cs;
	}
	for(int i = 0; i < as.size(); ++i)
		solve(as[i], bs[i], true);
}

Compilation message

minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = h; i < a.size(); ++i) lb.pb(a[i]);
      |                 ~~^~~~~~~~~~
minerals.cpp:47:9: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   47 |   if(cs == ls ^ in) ra.pb(i);
      |      ~~~^~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i = 0; i < as.size(); ++i)
      |                 ~~^~~~~~~~~~~
minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:47:9: warning: 'cs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |   if(cs == ls ^ in) ra.pb(i);
      |      ~~~^~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 548 KB Output is correct
2 Correct 24 ms 584 KB Output is correct
3 Correct 41 ms 744 KB Output is correct
4 Correct 77 ms 1052 KB Output is correct
5 Correct 144 ms 1580 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 272 KB Output is correct
5 Correct 11 ms 548 KB Output is correct
6 Correct 24 ms 584 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 77 ms 1052 KB Output is correct
9 Correct 144 ms 1580 KB Output is correct
10 Correct 10 ms 456 KB Output is correct
11 Correct 97 ms 1312 KB Output is correct
12 Correct 153 ms 1780 KB Output is correct
13 Correct 6 ms 2480 KB Output is correct
14 Correct 162 ms 1564 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 272 KB Output is correct
5 Correct 11 ms 548 KB Output is correct
6 Correct 24 ms 584 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 77 ms 1052 KB Output is correct
9 Correct 144 ms 1580 KB Output is correct
10 Correct 10 ms 456 KB Output is correct
11 Correct 97 ms 1312 KB Output is correct
12 Correct 153 ms 1780 KB Output is correct
13 Correct 6 ms 2480 KB Output is correct
14 Correct 162 ms 1564 KB Output is correct
15 Correct 392 ms 3592 KB Output is correct
16 Correct 392 ms 3528 KB Output is correct
17 Correct 14 ms 5844 KB Output is correct
18 Correct 377 ms 3392 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 272 KB Output is correct
5 Correct 11 ms 548 KB Output is correct
6 Correct 24 ms 584 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 77 ms 1052 KB Output is correct
9 Correct 144 ms 1580 KB Output is correct
10 Correct 10 ms 456 KB Output is correct
11 Correct 97 ms 1312 KB Output is correct
12 Correct 153 ms 1780 KB Output is correct
13 Correct 6 ms 2480 KB Output is correct
14 Correct 162 ms 1564 KB Output is correct
15 Correct 392 ms 3592 KB Output is correct
16 Correct 392 ms 3528 KB Output is correct
17 Correct 14 ms 5844 KB Output is correct
18 Correct 377 ms 3392 KB Output is correct
19 Correct 391 ms 3640 KB Output is correct
20 Correct 404 ms 3632 KB Output is correct
21 Correct 14 ms 6056 KB Output is correct
22 Correct 374 ms 3460 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 272 KB Output is correct
5 Correct 11 ms 548 KB Output is correct
6 Correct 24 ms 584 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 77 ms 1052 KB Output is correct
9 Correct 144 ms 1580 KB Output is correct
10 Correct 10 ms 456 KB Output is correct
11 Correct 97 ms 1312 KB Output is correct
12 Correct 153 ms 1780 KB Output is correct
13 Correct 6 ms 2480 KB Output is correct
14 Correct 162 ms 1564 KB Output is correct
15 Correct 392 ms 3592 KB Output is correct
16 Correct 392 ms 3528 KB Output is correct
17 Correct 14 ms 5844 KB Output is correct
18 Correct 377 ms 3392 KB Output is correct
19 Correct 391 ms 3640 KB Output is correct
20 Correct 404 ms 3632 KB Output is correct
21 Correct 14 ms 6056 KB Output is correct
22 Correct 374 ms 3460 KB Output is correct
23 Correct 418 ms 3636 KB Output is correct
24 Correct 411 ms 3696 KB Output is correct
25 Correct 14 ms 6184 KB Output is correct
26 Correct 386 ms 3484 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 272 KB Output is correct
5 Correct 11 ms 548 KB Output is correct
6 Correct 24 ms 584 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 77 ms 1052 KB Output is correct
9 Correct 144 ms 1580 KB Output is correct
10 Correct 10 ms 456 KB Output is correct
11 Correct 97 ms 1312 KB Output is correct
12 Correct 153 ms 1780 KB Output is correct
13 Correct 6 ms 2480 KB Output is correct
14 Correct 162 ms 1564 KB Output is correct
15 Correct 392 ms 3592 KB Output is correct
16 Correct 392 ms 3528 KB Output is correct
17 Correct 14 ms 5844 KB Output is correct
18 Correct 377 ms 3392 KB Output is correct
19 Correct 391 ms 3640 KB Output is correct
20 Correct 404 ms 3632 KB Output is correct
21 Correct 14 ms 6056 KB Output is correct
22 Correct 374 ms 3460 KB Output is correct
23 Correct 418 ms 3636 KB Output is correct
24 Correct 411 ms 3696 KB Output is correct
25 Correct 14 ms 6184 KB Output is correct
26 Correct 386 ms 3484 KB Output is correct
27 Correct 414 ms 3784 KB Output is correct
28 Correct 441 ms 3668 KB Output is correct
29 Correct 21 ms 6448 KB Output is correct
30 Correct 410 ms 3600 KB Output is correct

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 272 KB Output is correct
5 Correct 11 ms 548 KB Output is correct
6 Correct 24 ms 584 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 77 ms 1052 KB Output is correct
9 Correct 144 ms 1580 KB Output is correct
10 Correct 10 ms 456 KB Output is correct
11 Correct 97 ms 1312 KB Output is correct
12 Correct 153 ms 1780 KB Output is correct
13 Correct 6 ms 2480 KB Output is correct
14 Correct 162 ms 1564 KB Output is correct
15 Correct 392 ms 3592 KB Output is correct
16 Correct 392 ms 3528 KB Output is correct
17 Correct 14 ms 5844 KB Output is correct
18 Correct 377 ms 3392 KB Output is correct
19 Correct 391 ms 3640 KB Output is correct
20 Correct 404 ms 3632 KB Output is correct
21 Correct 14 ms 6056 KB Output is correct
22 Correct 374 ms 3460 KB Output is correct
23 Correct 418 ms 3636 KB Output is correct
24 Correct 411 ms 3696 KB Output is correct
25 Correct 14 ms 6184 KB Output is correct
26 Correct 386 ms 3484 KB Output is correct
27 Correct 414 ms 3784 KB Output is correct
28 Correct 441 ms 3668 KB Output is correct
29 Correct 21 ms 6448 KB Output is correct
30 Correct 410 ms 3600 KB Output is correct
31 Incorrect 412 ms 3732 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 272 KB Output is correct
5 Correct 11 ms 548 KB Output is correct
6 Correct 24 ms 584 KB Output is correct
7 Correct 41 ms 744 KB Output is correct
8 Correct 77 ms 1052 KB Output is correct
9 Correct 144 ms 1580 KB Output is correct
10 Correct 10 ms 456 KB Output is correct
11 Correct 97 ms 1312 KB Output is correct
12 Correct 153 ms 1780 KB Output is correct
13 Correct 6 ms 2480 KB Output is correct
14 Correct 162 ms 1564 KB Output is correct
15 Correct 392 ms 3592 KB Output is correct
16 Correct 392 ms 3528 KB Output is correct
17 Correct 14 ms 5844 KB Output is correct
18 Correct 377 ms 3392 KB Output is correct
19 Correct 391 ms 3640 KB Output is correct
20 Correct 404 ms 3632 KB Output is correct
21 Correct 14 ms 6056 KB Output is correct
22 Correct 374 ms 3460 KB Output is correct
23 Correct 418 ms 3636 KB Output is correct
24 Correct 411 ms 3696 KB Output is correct
25 Correct 14 ms 6184 KB Output is correct
26 Correct 386 ms 3484 KB Output is correct
27 Correct 414 ms 3784 KB Output is correct
28 Correct 441 ms 3668 KB Output is correct
29 Correct 21 ms 6448 KB Output is correct
30 Correct 410 ms 3600 KB Output is correct
31 Incorrect 412 ms 3732 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -