oj.uz

Submission #128174

# Submission time Handle Problem Language Result Execution time Memory
128174 2019-07-10T13:35:36 Z dndhk Minerals (JOI19_minerals) C++14
40 / 100
 18 ms 1912 KB 
#include "minerals.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 43000;

int idx[MAX_N*2+1];
vector<pii> ans;

bool chk[MAX_N+1];

vector<int> vt1, vt2;

void solve(int x, int y){
	/*printf("%d %d\n", x, y);
	for(int i=x; i<=y; i++){
		printf("%d ", idx[i]);
		if(i==(x+y)/2){
			printf("\n");
		}
	}
	printf("\n");*/
	if(y==x+1){
		ans.pb({idx[x], idx[y]});
		if(chk[x]){
			Query(idx[x]); Query(idx[y]);
		}
		return;
	}
	int l = (y-x+1)/2;
	int m = l/2;
	int i;
	if(chk[x]){
		int prv;
		i = x+l-1;
		while(m>0){
			prv = Query(idx[i]);
			i--; m--;
		}
		for(int j = y; j >= x+l; j--){
			int now = Query(idx[j]);
			if(now==prv){
				Query(idx[j]);
				vt1.push_back(idx[j]);
			}else{
				vt2.push_back(idx[j]);
			}
			prv = now;
		}
	}else{
		int prv;
		i = x;
		while(m>0){
			prv =  Query(idx[i]);
			chk[i] = true;
			m--; i++;
		}
		i--;
		for(int j=x+l; j<=y; j++){
			int now = Query(idx[j]);
			if(now==prv){
				vt1.push_back(idx[j]);
			}else{
				Query(idx[j]);
				vt2.push_back(idx[j]);
			}
		}
	}
	int i3 = i;
	int i2 = i+l;
	i = x+l-1;
	while(i>i3){
		chk[i2] = false;
		idx[i2] = idx[i];
		i--; i2--;
	}
	i2 = i + l+1;
	i = i3+1;
	while(!vt1.empty()){
		chk[i] = true;
		idx[i] = vt1.back(); vt1.pop_back(); i++;
	}
	while(!vt2.empty()){
		chk[i2] = false;
		idx[i2] = vt2.back(); vt2.pop_back(); i2++;
	}
	solve(x, i3*2 - x + 1); solve(i3*2 - x + 2, y);
}

void Solve(int N) {
	int prv = 0;
	int i1 = 1, i2 = N+1;
	for(int i=1; i<=N*2; i++){
		int now = Query(i);
		if(now==prv){
			idx[i2++] = i;
		}else{
			idx[i1++] = i;
		}
		prv = now;
	}
	for(int i=1; i<=N*2; i++)	Query(i);
	solve(1, N*2);
	for(int i=0; i<ans.size(); i++){
		Answer(ans[i].first, ans[i].second);
	}
}

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:124:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ans.size(); i++){
               ~^~~~~~~~~~~
minerals.cpp: In function 'void solve(int, int)':
minerals.cpp:81:4: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(now==prv){
    ^~
minerals.cpp:62:4: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(now==prv){
    ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 8 ms 808 KB Output is correct
5 Correct 15 ms 1144 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 15 ms 1144 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 10 ms 936 KB Output is correct
12 Correct 13 ms 1260 KB Output is correct
13 Correct 12 ms 1144 KB Output is correct
14 Correct 12 ms 1320 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 15 ms 1144 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 10 ms 936 KB Output is correct
12 Correct 13 ms 1260 KB Output is correct
13 Correct 12 ms 1144 KB Output is correct
14 Correct 12 ms 1320 KB Output is correct
15 Incorrect 18 ms 1912 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 15 ms 1144 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 10 ms 936 KB Output is correct
12 Correct 13 ms 1260 KB Output is correct
13 Correct 12 ms 1144 KB Output is correct
14 Correct 12 ms 1320 KB Output is correct
15 Incorrect 18 ms 1912 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 15 ms 1144 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 10 ms 936 KB Output is correct
12 Correct 13 ms 1260 KB Output is correct
13 Correct 12 ms 1144 KB Output is correct
14 Correct 12 ms 1320 KB Output is correct
15 Incorrect 18 ms 1912 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 15 ms 1144 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 10 ms 936 KB Output is correct
12 Correct 13 ms 1260 KB Output is correct
13 Correct 12 ms 1144 KB Output is correct
14 Correct 12 ms 1320 KB Output is correct
15 Incorrect 18 ms 1912 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 15 ms 1144 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 10 ms 936 KB Output is correct
12 Correct 13 ms 1260 KB Output is correct
13 Correct 12 ms 1144 KB Output is correct
14 Correct 12 ms 1320 KB Output is correct
15 Incorrect 18 ms 1912 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 15 ms 1144 KB Output is correct
10 Correct 0 ms 376 KB Output is correct
11 Correct 10 ms 936 KB Output is correct
12 Correct 13 ms 1260 KB Output is correct
13 Correct 12 ms 1144 KB Output is correct
14 Correct 12 ms 1320 KB Output is correct
15 Incorrect 18 ms 1912 KB Wrong Answer [1]
16 Halted 0 ms 0 KB -