oj.uz

Submission #128178

# Submission time Handle Problem Language Result Execution time Memory
128178 2019-07-10T13:38:57 Z dndhk Minerals (JOI19_minerals) C++14
40 / 100
 23 ms 3360 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;
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 248 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 248 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 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 8 ms 808 KB Output is correct
5 Correct 14 ms 1200 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 2 ms 296 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 14 ms 1200 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 10 ms 1016 KB Output is correct
12 Correct 15 ms 1336 KB Output is correct
13 Correct 10 ms 1328 KB Output is correct
14 Correct 12 ms 1272 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 2 ms 296 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 14 ms 1200 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 10 ms 1016 KB Output is correct
12 Correct 15 ms 1336 KB Output is correct
13 Correct 10 ms 1328 KB Output is correct
14 Correct 12 ms 1272 KB Output is correct
15 Runtime error 23 ms 3360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 2 ms 296 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 14 ms 1200 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 10 ms 1016 KB Output is correct
12 Correct 15 ms 1336 KB Output is correct
13 Correct 10 ms 1328 KB Output is correct
14 Correct 12 ms 1272 KB Output is correct
15 Runtime error 23 ms 3360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 2 ms 296 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 14 ms 1200 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 10 ms 1016 KB Output is correct
12 Correct 15 ms 1336 KB Output is correct
13 Correct 10 ms 1328 KB Output is correct
14 Correct 12 ms 1272 KB Output is correct
15 Runtime error 23 ms 3360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 2 ms 296 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 14 ms 1200 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 10 ms 1016 KB Output is correct
12 Correct 15 ms 1336 KB Output is correct
13 Correct 10 ms 1328 KB Output is correct
14 Correct 12 ms 1272 KB Output is correct
15 Runtime error 23 ms 3360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 2 ms 296 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 14 ms 1200 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 10 ms 1016 KB Output is correct
12 Correct 15 ms 1336 KB Output is correct
13 Correct 10 ms 1328 KB Output is correct
14 Correct 12 ms 1272 KB Output is correct
15 Runtime error 23 ms 3360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 2 ms 296 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 14 ms 1200 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 10 ms 1016 KB Output is correct
12 Correct 15 ms 1336 KB Output is correct
13 Correct 10 ms 1328 KB Output is correct
14 Correct 12 ms 1272 KB Output is correct
15 Runtime error 23 ms 3360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -