oj.uz

Submission #205245

# Submission time Handle Problem Language Result Execution time Memory
205245 2020-02-28T11:17:57 Z ics0503 Minerals (JOI19_minerals) C++17
6 / 100
 265 ms 262148 KB 
#include "minerals.h"
#include<vector>
using namespace std;
vector<int>L, R;
struct SEG {
	vector<int>L;
	int l, r, s, e, who, ck;
} seg[212121];
int segN = 1, segW[212121];
void make_seg(int now, int s, int e) {
	seg[now].who = s;
	seg[now].s = s; seg[now].e = e;
	if (s == e) {
		segW[s] = now;
		return;
	}
	int m = (s + e) / 2 + (e - s + 1) % 2;
	if (!seg[now].l)seg[now].l = ++segN;
	make_seg(seg[now].l, s, m);
	if (!seg[now].r)seg[now].r = ++segN;
	make_seg(seg[now].r, m + 1, e);
}
int is_in[212121];
void go_down(int now, int s, int e) {
	seg[now].ck = 1;
	if (s == e) return;
	int m = (s + e) / 2 + (e - s + 1) % 2, l = seg[now].l, r = seg[now].r, bef;
	for (int i = m + 1; i <= e; i++) {
		is_in[i] = !is_in[i];
		bef = Query(L[i]);
	}
	for (int p : seg[now].L) {
		if (seg[r].L.size() == (e - (m + 1) + 1)) { seg[l].L.push_back(p); continue; }
		if (seg[l].L.size() == (m - s + 1)) { seg[r].L.push_back(p); continue; }
		int res = Query(p);
		if (res == bef) {
			if (is_in[s])seg[l].L.push_back(p);
			else seg[r].L.push_back(p);
		}
		else {
			if (is_in[s])seg[r].L.push_back(p);
			else seg[l].L.push_back(p);
		}
		bef = res;
	}
	go_down(l, s, m);
}
void Solve(int n) {
	int cnt = 0;
	for (int i = 1; i <= n * 2; i++) {
		int res = Query(i);
		if (res != cnt) L.push_back(i);
		else seg[1].L.push_back(i);
		cnt = res;
	}
	for (int i = 0; i < n; i++)is_in[i] = 1;
	make_seg(1, 0, n - 1);
	go_down(1, 0, n - 1);
	for (int i = 2; i <= segN; i++) {
		int s = seg[i].s, e = seg[i].e;
		if (seg[i].ck || seg[i].L.empty() || s == e)continue;
		go_down(i, s, e);
	}
	for (int i = 0; i < n; i++) {
		for (int p : seg[segW[i]].L) {
			Answer(L[i], p);
		}
	}
}

Compilation message

minerals.cpp: In function 'void go_down(int, int, int)':
minerals.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (seg[r].L.size() == (e - (m + 1) + 1)) { seg[l].L.push_back(p); continue; }
       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
minerals.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (seg[l].L.size() == (m - s + 1)) { seg[r].L.push_back(p); continue; }
       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
minerals.cpp:36:3: warning: 'bef' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (res == bef) {
   ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 11 ms 10360 KB Output is correct
4 Correct 11 ms 10360 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10360 KB Output is correct
2 Correct 13 ms 10488 KB Output is correct
3 Correct 15 ms 10744 KB Output is correct
4 Correct 21 ms 11512 KB Output is correct
5 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 11 ms 10360 KB Output is correct
4 Correct 11 ms 10360 KB Output is correct
5 Correct 11 ms 10360 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 15 ms 10744 KB Output is correct
8 Correct 21 ms 11512 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 11 ms 10360 KB Output is correct
4 Correct 11 ms 10360 KB Output is correct
5 Correct 11 ms 10360 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 15 ms 10744 KB Output is correct
8 Correct 21 ms 11512 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 11 ms 10360 KB Output is correct
4 Correct 11 ms 10360 KB Output is correct
5 Correct 11 ms 10360 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 15 ms 10744 KB Output is correct
8 Correct 21 ms 11512 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 11 ms 10360 KB Output is correct
4 Correct 11 ms 10360 KB Output is correct
5 Correct 11 ms 10360 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 15 ms 10744 KB Output is correct
8 Correct 21 ms 11512 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 11 ms 10360 KB Output is correct
4 Correct 11 ms 10360 KB Output is correct
5 Correct 11 ms 10360 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 15 ms 10744 KB Output is correct
8 Correct 21 ms 11512 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 11 ms 10360 KB Output is correct
4 Correct 11 ms 10360 KB Output is correct
5 Correct 11 ms 10360 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 15 ms 10744 KB Output is correct
8 Correct 21 ms 11512 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10232 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 11 ms 10360 KB Output is correct
4 Correct 11 ms 10360 KB Output is correct
5 Correct 11 ms 10360 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 15 ms 10744 KB Output is correct
8 Correct 21 ms 11512 KB Output is correct
9 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)