oj.uz

Submission #489828

# Submission time Handle Problem Language Result Execution time Memory
489828 2021-11-24T20:53:21 Z Fran1024 Minerals (JOI19_minerals) C++14
40 / 100
 128 ms 4568 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 0 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 516 KB Output is correct
3 Correct 14 ms 868 KB Output is correct
4 Correct 34 ms 1244 KB Output is correct
5 Correct 59 ms 1952 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 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 516 KB Output is correct
7 Correct 14 ms 868 KB Output is correct
8 Correct 34 ms 1244 KB Output is correct
9 Correct 59 ms 1952 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 40 ms 1364 KB Output is correct
12 Correct 69 ms 1940 KB Output is correct
13 Correct 61 ms 1952 KB Output is correct
14 Correct 56 ms 1888 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 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 516 KB Output is correct
7 Correct 14 ms 868 KB Output is correct
8 Correct 34 ms 1244 KB Output is correct
9 Correct 59 ms 1952 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 40 ms 1364 KB Output is correct
12 Correct 69 ms 1940 KB Output is correct
13 Correct 61 ms 1952 KB Output is correct
14 Correct 56 ms 1888 KB Output is correct
15 Incorrect 128 ms 4568 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 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 516 KB Output is correct
7 Correct 14 ms 868 KB Output is correct
8 Correct 34 ms 1244 KB Output is correct
9 Correct 59 ms 1952 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 40 ms 1364 KB Output is correct
12 Correct 69 ms 1940 KB Output is correct
13 Correct 61 ms 1952 KB Output is correct
14 Correct 56 ms 1888 KB Output is correct
15 Incorrect 128 ms 4568 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 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 516 KB Output is correct
7 Correct 14 ms 868 KB Output is correct
8 Correct 34 ms 1244 KB Output is correct
9 Correct 59 ms 1952 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 40 ms 1364 KB Output is correct
12 Correct 69 ms 1940 KB Output is correct
13 Correct 61 ms 1952 KB Output is correct
14 Correct 56 ms 1888 KB Output is correct
15 Incorrect 128 ms 4568 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 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 516 KB Output is correct
7 Correct 14 ms 868 KB Output is correct
8 Correct 34 ms 1244 KB Output is correct
9 Correct 59 ms 1952 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 40 ms 1364 KB Output is correct
12 Correct 69 ms 1940 KB Output is correct
13 Correct 61 ms 1952 KB Output is correct
14 Correct 56 ms 1888 KB Output is correct
15 Incorrect 128 ms 4568 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 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 516 KB Output is correct
7 Correct 14 ms 868 KB Output is correct
8 Correct 34 ms 1244 KB Output is correct
9 Correct 59 ms 1952 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 40 ms 1364 KB Output is correct
12 Correct 69 ms 1940 KB Output is correct
13 Correct 61 ms 1952 KB Output is correct
14 Correct 56 ms 1888 KB Output is correct
15 Incorrect 128 ms 4568 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 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 516 KB Output is correct
7 Correct 14 ms 868 KB Output is correct
8 Correct 34 ms 1244 KB Output is correct
9 Correct 59 ms 1952 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 40 ms 1364 KB Output is correct
12 Correct 69 ms 1940 KB Output is correct
13 Correct 61 ms 1952 KB Output is correct
14 Correct 56 ms 1888 KB Output is correct
15 Incorrect 128 ms 4568 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -