Submission #406488

#	Time	Username	Problem	Language	Result	Execution time	Memory
406488		atoiz	Nicelines (RMI20_nicelines)	C++14	0 / 100	2 ms	280 KiB

nicelines

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
 
#include "nice_lines.h"
 
const int X = 100000;
 
bool equals(long double x, long double y) { return std::abs(x - y) < 0.001; }
 
void add(int64_t Y, std::vector<int> &A, std::vector<int> &B) {
	int b = int(Y % X);
	while (b > 10000) b -= X;
	while (b < -10000) b += X;
	A.push_back((Y - b) / X), B.push_back(b);
}

int64_t roundDouble(long double x) {
    if (x < 0) return -int64_t(0.5 - x);
    else return int64_t(x + 0.5);
}
 
void solve_range(int64_t lo, long double dist_lo_0, long double dist_lo_1, int64_t hi, long double dist_hi_0, long double dist_hi_1, std::vector<int> &a, std::vector<int> &b) {
	long double slope_lo = dist_lo_1 - dist_lo_0, slope_hi = dist_hi_0 - dist_hi_1;
	if (lo + 1 >= hi) return;
	// if (equals(slope_lo, slope_hi)) return;
 
	int64_t md = roundDouble(((dist_lo_0 - slope_lo * lo) - (dist_hi_0 - slope_hi * hi)) / (slope_hi - slope_lo));
	fprintf(stderr, "%lld %lld\n", lo, hi);
    fprintf(stderr, "%.10lf %.10lf\n", double(slope_lo), double(slope_hi));
    fprintf(stderr, "%lf\n", double(((dist_lo_0 - slope_lo * lo) - (dist_hi_0 - slope_hi * hi)) / (slope_hi - slope_lo)));
    fprintf(stderr, "%lld\n", md);

	long double dist_md_0 = query(X, md);
    fprintf(stderr, "%.10lf\n", double(dist_md_0));
    fprintf(stderr, "%.10lf\n", double(dist_lo_0 + (md - lo) * slope_lo));
    fprintf(stderr, "%.10lf\n", double(dist_hi_0 + (md - hi) * slope_hi));
 
	if (equals(dist_md_0, dist_lo_0 + (md - lo) * slope_lo) && equals(dist_md_0, dist_hi_0 + (md - hi) * slope_hi)) {
		add(md, a, b);
		return;
	}
 
	long double dist_md_1 = query(X, md + 1);
 
	if (equals(dist_md_1, dist_lo_0 + (md + 1 - lo) * slope_lo) && equals(dist_md_1, dist_hi_0 + (md + 1 - hi) * slope_hi)) {
		add(md + 1, a, b);
		return;
	}
    return;
 
	solve_range(lo, dist_lo_0, dist_lo_1, md + 1, dist_md_1, dist_md_0, a, b);
	solve_range(md, dist_md_0, dist_md_1, hi, dist_hi_0, dist_hi_1, a, b);
}
 
void solve(int subtask_id, int N) {
	int64_t lo = -1000020000ll, hi = 1000020000ll;
	std::vector<int> a, b;
	solve_range(lo, query(X, lo), query(X, lo + 1), hi, query(X, hi), query(X, hi - 1), a, b);
    the_lines_are(a, b);
}

Compilation message (stderr)

nicelines.cpp: In function 'void solve_range(int64_t, long double, long double, int64_t, long double, long double, std::vector<int>&, std::vector<int>&)':
nicelines.cpp:30:22: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int64_t' {aka 'long int'} [-Wformat=]
   30 |  fprintf(stderr, "%lld %lld\n", lo, hi);
      |                   ~~~^          ~~
      |                      |          |
      |                      |          int64_t {aka long int}
      |                      long long int
      |                   %ld
nicelines.cpp:30:27: warning: format '%lld' expects argument of type 'long long int', but argument 4 has type 'int64_t' {aka 'long int'} [-Wformat=]
   30 |  fprintf(stderr, "%lld %lld\n", lo, hi);
      |                        ~~~^         ~~
      |                           |         |
      |                           |         int64_t {aka long int}
      |                           long long int
      |                        %ld
nicelines.cpp:33:25: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int64_t' {aka 'long int'} [-Wformat=]
   33 |     fprintf(stderr, "%lld\n", md);
      |                      ~~~^     ~~
      |                         |     |
      |                         |     int64_t {aka long int}
      |                         long long int
      |                      %ld

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27