oj.uz

Submission #489823

# Submission time Handle Problem Language Result Execution time Memory
489823 2021-11-24T20:46:11 Z Fran1024 Minerals (JOI19_minerals) C++14
40 / 100
 130 ms 4440 KB 
#include "minerals.h"
#include <vector>
#include <set>
#include <stdio.h>
using namespace std;

set <int> stroj;
int MCNT = 0;

void ubaciniz(vector <int> &v) {
	set <int> unizu;
	for(int i = 0; i < v.size(); i++) {
		unizu.insert(v[i]);
	}
	vector <int> pobrisani;
	for(auto it = stroj.begin(); it != stroj.end(); it++) {
		if(unizu.find(*it) == unizu.end()) {
			Query(*it);
			pobrisani.push_back(*it);
		}
	}
	for(int i = 0; i < pobrisani.size(); i++) {
		stroj.erase(pobrisani[i]);
	}
	for(int i = 0; i < v.size(); i++) {
		if(stroj.find(v[i]) == stroj.end()) {
			Query(v[i]);
			stroj.insert(v[i]);
		}
	}
}

int ubaci(int x) {
	if(stroj.find(x) == stroj.end()) {
		stroj.insert(x);
		return MCNT = Query(x);
	}
	return MCNT;
}

void izvadi(int x) {
	if(stroj.find(x) != stroj.end()) {
		stroj.erase(x);
		MCNT = Query(x);
	}
}

void divcon(vector <int> &a, vector <int> &b) {
	if(a.size() == 1) {
		Answer(a[0], b[0]);
		return;
	}
    /*printf("a.size() = %d, b.size() = %d\n", a.size(), b.size());*/
	vector <int> a1;
	vector <int> b1;
	vector <int> a2;
	vector <int> b2;
	for(int i = 0; i < a.size() / 2; i++) {
		a1.push_back(a[i]);
	}
	for(int i = a.size() / 2; i < a.size(); i++) {
		a2.push_back(a[i]);
	}
	ubaciniz(a1);
	for(int i = 0; i < b.size(); i++) {
		if(ubaci(b[i]) > a1.size()) {
			b2.push_back(b[i]);
		} else {
			b1.push_back(b[i]);
		}
		izvadi(b[i]);
	}
	divcon(a1, b1);
	divcon(a2, b2);
}

void Solve(int N) {
	 vector <int> a;
	 vector <int> b;
	 for(int i = 1; i <= 2 * N; i++) {
	 	ubaci(i);
	 	if(MCNT == a.size()) {
	 		izvadi(i);
	 		b.push_back(i);
		 } else {
		 	a.push_back(i);
		 }
	 }
	 //printf("a.size() = %d\n", a.size());
	 divcon(a, b);
}

Compilation message

minerals.cpp: In function 'void ubaciniz(std::vector<int>&)':
minerals.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i = 0; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
minerals.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0; i < pobrisani.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~
minerals.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 0; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
minerals.cpp: In function 'void divcon(std::vector<int>&, std::vector<int>&)':
minerals.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0; i < a.size() / 2; i++) {
      |                 ~~^~~~~~~~~~~~~~
minerals.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = a.size() / 2; i < a.size(); i++) {
      |                            ~~^~~~~~~~~~
minerals.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = 0; i < b.size(); i++) {
      |                 ~~^~~~~~~~~~
minerals.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   if(ubaci(b[i]) > a1.size()) {
      |      ~~~~~~~~~~~~^~~~~~~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:82:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    if(MCNT == a.size()) {
      |       ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 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 3 ms 328 KB Output is correct
2 Correct 6 ms 456 KB Output is correct
3 Correct 12 ms 752 KB Output is correct
4 Correct 28 ms 1196 KB Output is correct
5 Correct 58 ms 1888 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 12 ms 752 KB Output is correct
8 Correct 28 ms 1196 KB Output is correct
9 Correct 58 ms 1888 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 39 ms 1412 KB Output is correct
12 Correct 57 ms 1984 KB Output is correct
13 Correct 62 ms 1892 KB Output is correct
14 Correct 55 ms 1864 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 12 ms 752 KB Output is correct
8 Correct 28 ms 1196 KB Output is correct
9 Correct 58 ms 1888 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 39 ms 1412 KB Output is correct
12 Correct 57 ms 1984 KB Output is correct
13 Correct 62 ms 1892 KB Output is correct
14 Correct 55 ms 1864 KB Output is correct
15 Incorrect 130 ms 4440 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 12 ms 752 KB Output is correct
8 Correct 28 ms 1196 KB Output is correct
9 Correct 58 ms 1888 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 39 ms 1412 KB Output is correct
12 Correct 57 ms 1984 KB Output is correct
13 Correct 62 ms 1892 KB Output is correct
14 Correct 55 ms 1864 KB Output is correct
15 Incorrect 130 ms 4440 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 12 ms 752 KB Output is correct
8 Correct 28 ms 1196 KB Output is correct
9 Correct 58 ms 1888 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 39 ms 1412 KB Output is correct
12 Correct 57 ms 1984 KB Output is correct
13 Correct 62 ms 1892 KB Output is correct
14 Correct 55 ms 1864 KB Output is correct
15 Incorrect 130 ms 4440 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 12 ms 752 KB Output is correct
8 Correct 28 ms 1196 KB Output is correct
9 Correct 58 ms 1888 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 39 ms 1412 KB Output is correct
12 Correct 57 ms 1984 KB Output is correct
13 Correct 62 ms 1892 KB Output is correct
14 Correct 55 ms 1864 KB Output is correct
15 Incorrect 130 ms 4440 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 12 ms 752 KB Output is correct
8 Correct 28 ms 1196 KB Output is correct
9 Correct 58 ms 1888 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 39 ms 1412 KB Output is correct
12 Correct 57 ms 1984 KB Output is correct
13 Correct 62 ms 1892 KB Output is correct
14 Correct 55 ms 1864 KB Output is correct
15 Incorrect 130 ms 4440 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 12 ms 752 KB Output is correct
8 Correct 28 ms 1196 KB Output is correct
9 Correct 58 ms 1888 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 39 ms 1412 KB Output is correct
12 Correct 57 ms 1984 KB Output is correct
13 Correct 62 ms 1892 KB Output is correct
14 Correct 55 ms 1864 KB Output is correct
15 Incorrect 130 ms 4440 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -