oj.uz

Submission #829310

# Submission time Handle Problem Language Result Execution time Memory
829310 2023-08-18T08:40:38 Z rainboy Nicelines (RMI20_nicelines) C++17
91.6766 / 100
 35 ms 284 KB 
#include "nice_lines.h"
#include <cmath>
#include <vector>

using namespace std;

typedef long double ld;
typedef vector<int> vi;

const int N = 100;
const int M = 10000;
const int X = 10000000;
const ld eps = 1e-9;

void solve(int subtask_id, int n) {
	int a_ = -(M + 1);
	ld u1 = query(X, (long long) -(M + 1) * X + M), u2 = query(X, (long long) -M * X - M);
	vi aa(n), bb(n);
	for (int i = 0; i < n; i++) {
		int lower = a_, upper = M + 1;
		ld v1_ = -1, v2_ = -1;
		while (upper - lower > 1) {
			int a = (lower + upper) / 2;
			ld v1 = query(X, (long long) a * X + M), v2 = query(X, (long long) (a + 1) * X - M);
			if (fabsl(((v2 - v1) - (u2 - u1)) / (X - M * 2)) < eps)
				lower = a;
			else
				upper = a, v1_ = v1, v2_ = v2;
		}
		int a = upper;
		ld v1 = v1_, v2 = v2_;
		long long y1 = (long long) (a_ + 1) * X - M, y2 = (long long) a * X + M;
		int b = roundl(((X - M * 2) * (v1 - u2) + y1 * (u2 - u1) - y2 * (v2 - v1)) / ((u2 - u1) - (v2 - v1)) - (ld) a * X);
		aa[i] = a, bb[i] = b;
		a_ = a, u1 = v1, u2 = v2;
	}
	the_lines_are(aa, bb);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 284 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #3
7.0 / 7.0

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

Subtask #4
15.8378203784 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 32 ms 208 KB Output is partially correct
2 Partially correct 32 ms 208 KB Output is partially correct
3 Partially correct 30 ms 208 KB Output is partially correct
4 Partially correct 35 ms 208 KB Output is partially correct

Subtask #5
22.3323817462 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 208 KB Output is partially correct
2 Partially correct 13 ms 208 KB Output is partially correct
3 Partially correct 9 ms 208 KB Output is partially correct
4 Partially correct 10 ms 208 KB Output is partially correct

Subtask #6
22.5063763272 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 32 ms 208 KB Output is partially correct
2 Partially correct 32 ms 208 KB Output is partially correct
3 Partially correct 30 ms 208 KB Output is partially correct
4 Partially correct 35 ms 208 KB Output is partially correct
5 Partially correct 10 ms 208 KB Output is partially correct
6 Partially correct 13 ms 208 KB Output is partially correct
7 Partially correct 9 ms 208 KB Output is partially correct
8 Partially correct 10 ms 208 KB Output is partially correct
9 Partially correct 28 ms 208 KB Output is partially correct
10 Partially correct 32 ms 208 KB Output is partially correct
11 Partially correct 23 ms 208 KB Output is partially correct
12 Partially correct 25 ms 208 KB Output is partially correct