oj.uz

Submission #516055

# Submission time Handle Problem Language Result Execution time Memory
516055 2022-01-20T10:44:59 Z lovrot Minerals (JOI19_minerals) C++14
40 / 100
 32 ms 2620 KB 
#include <bits/stdc++.h> 
#include "minerals.h"

#define vec vector
#define siz size()
#define pri(i, poc, n, pov) for(int i = (int) poc; i < (int) n; i += (int) pov)
#define pb push_back 
#define X first
#define Y second 

using namespace std;

const int N = 43010;

//bool on[N];
//int query_ans;
int qans;
vec<pair<int, int>> ans;
map<int, int> ans_esp;

/*
int Query(int x){
	int y = ans_esp[x]; 
		
	if(!on[x]){ 
		if(!on[y])
			query_ans++;
		on[x] = 1;
	}
	else{ 
		if(!on[y])
			query_ans--;
		on[x] = 0;
	}	

	//cout << "on query " << x << " " << query_ans << " " << query_ans - qans << "\n";

	return query_ans;
}*/

void divcon(vec<int> &a, vec<int> &b){	
	if(a.siz == 1){ 
		//ans.pb({a[0], b[0]});
		Answer(a[0], b[0]);
		return;
	}
	if(!a.siz){ 
		return;
	}

	vec<int> a_left;
	vec<int> b_left;
	vec<int> a_rght;
	vec<int> b_rght;

	int h = a.siz / 2;
	int raz, newans, pom;

	pri(i, 0, a.siz, 1){
		if(i < h){ 
			newans = Query(a[i]);
			raz = newans - qans;
			qans = newans;

			a_left.pb(a[i]);
		}
		else 
			a_rght.pb(a[i]);
	}

	/*if(raz != 0 && raz != 1)
		cout << "f\n";
	*/

	pri(i, 0, a.siz, 1){ 
		newans = Query(b[i]);
		pom = newans - qans;

		if((raz == 0 && pom == -1) || (raz == 1 && pom == 0)) 
			b_left.pb(b[i]);
		else{
			newans = Query(b[i]);
			b_rght.pb(b[i]);
		}
		qans = newans;
	}
	/*
	for(int i : a)
		cout << i << " ";
	cout << "\n";
	for(int i : b)
		cout << i << " ";
	cout << "\n";


	for(int i : a_left)
		cout << i << " ";
	cout << "\n";
	for(int i : b_left)
		cout << i << " ";
	cout << "\n\n";

	for(int i : a_rght)
		cout << i << " ";
	cout << "\n";
	for(int i : b_rght)
		cout << i << " ";
	cout << "\n---------------\n"; */

	divcon(a_left, b_left);
	divcon(a_rght, b_rght);	
}

void Solve(int n){ 
	vec<int> a;
	vec<int> b;

	int newans;
	
	pri(i, 1, n * 2 + 1, 1){
		newans = Query(i);
		if(newans - qans){
			a.pb(i);
		}
		else{ 
			b.pb(i);
		}	
		qans = newans;
	}	

	divcon(a, b);
}
/*
int main(){ 
	ios_base::sync_with_stdio(0);

	int n;

	cin >> n;

	for(int i = 0; i < n; i++){ 
		int x, y;
		cin >> x >> y;
		ans_esp[x] = y;
		ans_esp[y] = x;
	}

	Solve(n);

	for(int i = 0; i < n; i++){ 
		int x = ans[i].X;
		int y = ans[i].Y;

		if(ans_esp[x] != y && ans_esp[y] != x){ 
			cout << "Invalid\n";
			exit(0);
		}
	}

	cout << "Correct\n";
	return 0;
}
*/

Compilation message

minerals.cpp: In function 'void divcon(std::vector<int>&, std::vector<int>&)':
minerals.cpp:79:38: warning: 'raz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |   if((raz == 0 && pom == -1) || (raz == 1 && pom == 0))
      |                                  ~~~~^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 200 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 3 ms 328 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 7 ms 676 KB Output is correct
5 Correct 15 ms 1096 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 7 ms 676 KB Output is correct
9 Correct 15 ms 1096 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 840 KB Output is correct
12 Correct 13 ms 1096 KB Output is correct
13 Correct 11 ms 1096 KB Output is correct
14 Correct 11 ms 1020 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 7 ms 676 KB Output is correct
9 Correct 15 ms 1096 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 840 KB Output is correct
12 Correct 13 ms 1096 KB Output is correct
13 Correct 11 ms 1096 KB Output is correct
14 Correct 11 ms 1020 KB Output is correct
15 Incorrect 32 ms 2620 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 7 ms 676 KB Output is correct
9 Correct 15 ms 1096 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 840 KB Output is correct
12 Correct 13 ms 1096 KB Output is correct
13 Correct 11 ms 1096 KB Output is correct
14 Correct 11 ms 1020 KB Output is correct
15 Incorrect 32 ms 2620 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 7 ms 676 KB Output is correct
9 Correct 15 ms 1096 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 840 KB Output is correct
12 Correct 13 ms 1096 KB Output is correct
13 Correct 11 ms 1096 KB Output is correct
14 Correct 11 ms 1020 KB Output is correct
15 Incorrect 32 ms 2620 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 7 ms 676 KB Output is correct
9 Correct 15 ms 1096 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 840 KB Output is correct
12 Correct 13 ms 1096 KB Output is correct
13 Correct 11 ms 1096 KB Output is correct
14 Correct 11 ms 1020 KB Output is correct
15 Incorrect 32 ms 2620 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 7 ms 676 KB Output is correct
9 Correct 15 ms 1096 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 840 KB Output is correct
12 Correct 13 ms 1096 KB Output is correct
13 Correct 11 ms 1096 KB Output is correct
14 Correct 11 ms 1020 KB Output is correct
15 Incorrect 32 ms 2620 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 4 ms 456 KB Output is correct
8 Correct 7 ms 676 KB Output is correct
9 Correct 15 ms 1096 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 840 KB Output is correct
12 Correct 13 ms 1096 KB Output is correct
13 Correct 11 ms 1096 KB Output is correct
14 Correct 11 ms 1020 KB Output is correct
15 Incorrect 32 ms 2620 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -