oj.uz

Submission #489832

# Submission time Handle Problem Language Result Execution time Memory
489832 2021-11-24T20:56:42 Z Fran1024 Minerals (JOI19_minerals) C++14
40 / 100
 136 ms 6504 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++) {
        int oldMCNT = MCNT;
	 	ubaci(i);
	 	if(MCNT == oldMCNT) {
	 		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()) {
      |      ~~~~~~~~~~~~^~~~~~~~~~~

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 456 KB Output is correct
2 Correct 6 ms 584 KB Output is correct
3 Correct 15 ms 976 KB Output is correct
4 Correct 32 ms 1564 KB Output is correct
5 Correct 60 ms 2660 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 456 KB Output is correct
6 Correct 6 ms 584 KB Output is correct
7 Correct 15 ms 976 KB Output is correct
8 Correct 32 ms 1564 KB Output is correct
9 Correct 60 ms 2660 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 40 ms 1948 KB Output is correct
12 Correct 62 ms 2760 KB Output is correct
13 Correct 65 ms 2720 KB Output is correct
14 Correct 57 ms 2648 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 456 KB Output is correct
6 Correct 6 ms 584 KB Output is correct
7 Correct 15 ms 976 KB Output is correct
8 Correct 32 ms 1564 KB Output is correct
9 Correct 60 ms 2660 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 40 ms 1948 KB Output is correct
12 Correct 62 ms 2760 KB Output is correct
13 Correct 65 ms 2720 KB Output is correct
14 Correct 57 ms 2648 KB Output is correct
15 Incorrect 136 ms 6504 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 456 KB Output is correct
6 Correct 6 ms 584 KB Output is correct
7 Correct 15 ms 976 KB Output is correct
8 Correct 32 ms 1564 KB Output is correct
9 Correct 60 ms 2660 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 40 ms 1948 KB Output is correct
12 Correct 62 ms 2760 KB Output is correct
13 Correct 65 ms 2720 KB Output is correct
14 Correct 57 ms 2648 KB Output is correct
15 Incorrect 136 ms 6504 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 456 KB Output is correct
6 Correct 6 ms 584 KB Output is correct
7 Correct 15 ms 976 KB Output is correct
8 Correct 32 ms 1564 KB Output is correct
9 Correct 60 ms 2660 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 40 ms 1948 KB Output is correct
12 Correct 62 ms 2760 KB Output is correct
13 Correct 65 ms 2720 KB Output is correct
14 Correct 57 ms 2648 KB Output is correct
15 Incorrect 136 ms 6504 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 456 KB Output is correct
6 Correct 6 ms 584 KB Output is correct
7 Correct 15 ms 976 KB Output is correct
8 Correct 32 ms 1564 KB Output is correct
9 Correct 60 ms 2660 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 40 ms 1948 KB Output is correct
12 Correct 62 ms 2760 KB Output is correct
13 Correct 65 ms 2720 KB Output is correct
14 Correct 57 ms 2648 KB Output is correct
15 Incorrect 136 ms 6504 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 456 KB Output is correct
6 Correct 6 ms 584 KB Output is correct
7 Correct 15 ms 976 KB Output is correct
8 Correct 32 ms 1564 KB Output is correct
9 Correct 60 ms 2660 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 40 ms 1948 KB Output is correct
12 Correct 62 ms 2760 KB Output is correct
13 Correct 65 ms 2720 KB Output is correct
14 Correct 57 ms 2648 KB Output is correct
15 Incorrect 136 ms 6504 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 456 KB Output is correct
6 Correct 6 ms 584 KB Output is correct
7 Correct 15 ms 976 KB Output is correct
8 Correct 32 ms 1564 KB Output is correct
9 Correct 60 ms 2660 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 40 ms 1948 KB Output is correct
12 Correct 62 ms 2760 KB Output is correct
13 Correct 65 ms 2720 KB Output is correct
14 Correct 57 ms 2648 KB Output is correct
15 Incorrect 136 ms 6504 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -