oj.uz

Submission #496609

# Submission time Handle Problem Language Result Execution time Memory
496609 2021-12-21T16:03:06 Z ignaciocanta Xylophone (JOI18_xylophone) C++14
0 / 100
 2000 ms 200 KB 
#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;

static int A[5000];

void solve(int n) {
	int low = 1, high = n;
	while(high - low > 1){
		int mid = low + (high - low) / 2;
		if(query(1, mid) == n - 1) high = mid;
		else low = mid;
	}
	int posN = high;
	low = 1, high = n;
	while(high - low > 1){
		int mid = low + (high - low) / 2;
		if(query(mid, n) == n - 1) low = mid;
		else high = mid;
	}
	vector<set<int>> cands(n+1);
	vector<bool> seen(n+1, 0), use(n+1, 0);
	cands[posN].insert(n);
	cands[low].insert(1);
	int tot = 0;
	while(tot < n){
		int todo = -1;
		for(int i = 1; i <= n; ++i){
			if(int(cands[i].size()) == 1 && !use[i]){
				todo = *cands[i].begin();
				use[i] = 1;
				//cout << "En " << i << " va " << todo << "\n";
				answer(i, *cands[i].begin());
				seen[todo] = 1;
				++tot;
				if(i + 1 <= n && !use[i+1]){
					int r1 = query(i, i+1);
					if(todo + r1 <= n && !seen[todo+r1]){
						cands[i+1].insert(todo+r1);
					}
					if(todo - r1 >= 1 && !seen[todo-r1]){
						cands[i+1].insert(todo-r1);
					}
				}
				if(i - 1 >= 1 && !use[i-1]){
					int r1 = query(i-1, i);
					if(todo + r1 <= n && !seen[todo+r1]){
						cands[i-1].insert(todo+r1);
					}
					if(todo - r1 >= 1 && !seen[todo-r1]){
						cands[i-1].insert(todo-r1);
					}
				}
				break;
			}
		}
		for(int i = 1; i <= n; ++i){
			if(cands[i].count(todo)){
				cands[i].erase(todo);
			}
		}
	}
}

Compilation message

xylophone.cpp:5:12: warning: 'A' defined but not used [-Wunused-variable]
    5 | static int A[5000];
      |            ^

Subtask #1
0 / 11.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 Execution timed out 3066 ms 200 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.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 Execution timed out 3066 ms 200 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.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 Execution timed out 3066 ms 200 KB Time limit exceeded
4 Halted 0 ms 0 KB -