oj.uz

Submission #128179

# Submission time Handle Problem Language Result Execution time Memory
128179 2019-07-10T13:39:26 Z dndhk Minerals (JOI19_minerals) C++14
40 / 100
 35 ms 1872 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*2+1];

vector<int> vt1, vt2;
int N;

deque<pii> dq;

void solve(){
	/*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");*/
	dq.pb({1, 2*N});
	int x, y;
	while(!dq.empty()){
		x = dq.front().first; y = dq.front().second; dq.pop_front();
		if(y==x+1){
			ans.pb({idx[x], idx[y]});
			if(chk[x]){
				Query(idx[x]); Query(idx[y]);
			}
			continue;
		}
		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++;
		}
		dq.pb({x, i3*2 - x + 1}); dq.pb({i3*2 - x + 2, y});
	}
}

void Solve(int n) {
	N = 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();
	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:133: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()':
minerals.cpp:88:5: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(now==prv){
     ^~
minerals.cpp:69:5: 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 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 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 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 8 ms 772 KB Output is correct
5 Correct 14 ms 1400 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 8 ms 772 KB Output is correct
9 Correct 14 ms 1400 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 10 ms 1144 KB Output is correct
12 Correct 15 ms 1320 KB Output is correct
13 Correct 12 ms 1400 KB Output is correct
14 Correct 12 ms 1276 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 8 ms 772 KB Output is correct
9 Correct 14 ms 1400 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 10 ms 1144 KB Output is correct
12 Correct 15 ms 1320 KB Output is correct
13 Correct 12 ms 1400 KB Output is correct
14 Correct 12 ms 1276 KB Output is correct
15 Incorrect 35 ms 1872 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 8 ms 772 KB Output is correct
9 Correct 14 ms 1400 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 10 ms 1144 KB Output is correct
12 Correct 15 ms 1320 KB Output is correct
13 Correct 12 ms 1400 KB Output is correct
14 Correct 12 ms 1276 KB Output is correct
15 Incorrect 35 ms 1872 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 8 ms 772 KB Output is correct
9 Correct 14 ms 1400 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 10 ms 1144 KB Output is correct
12 Correct 15 ms 1320 KB Output is correct
13 Correct 12 ms 1400 KB Output is correct
14 Correct 12 ms 1276 KB Output is correct
15 Incorrect 35 ms 1872 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 8 ms 772 KB Output is correct
9 Correct 14 ms 1400 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 10 ms 1144 KB Output is correct
12 Correct 15 ms 1320 KB Output is correct
13 Correct 12 ms 1400 KB Output is correct
14 Correct 12 ms 1276 KB Output is correct
15 Incorrect 35 ms 1872 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 8 ms 772 KB Output is correct
9 Correct 14 ms 1400 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 10 ms 1144 KB Output is correct
12 Correct 15 ms 1320 KB Output is correct
13 Correct 12 ms 1400 KB Output is correct
14 Correct 12 ms 1276 KB Output is correct
15 Incorrect 35 ms 1872 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 8 ms 772 KB Output is correct
9 Correct 14 ms 1400 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 10 ms 1144 KB Output is correct
12 Correct 15 ms 1320 KB Output is correct
13 Correct 12 ms 1400 KB Output is correct
14 Correct 12 ms 1276 KB Output is correct
15 Incorrect 35 ms 1872 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -