oj.uz

답안 #398548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398548 2021-05-04T13:50:55 Z model_code Nicelines (RMI20_nicelines) C++17
100 / 100
 8 ms 328 KB 
/**
* user:  wald-245
* fname: Almog
* lname: Wald
* task:  NiceLines
* score: 100.0
* date:  2020-12-04 11:28:51.779588
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#define forr(i,a,b,c) for(int i=a;i<b;i+=c)
#define fort(i,a,b) forr(i,a,b,1)
#define forn(i,n) fort(i,1,n)
#define fori(i,n) fort(i,0,n)
#define forin(i,arr) fori(i,arr.size())
#define forit(i,arr) for(auto i=arr.begin();i!=arr.end();i++)
#define forrb(i,a,b,c) for(int i=b-1;i>=a;i-=c)
#define fortb(i,a,b) forrb(i,a,b,1)
#define fornb(i,n) fortb(i,1,n)
#define forib(i,n) fortb(i,0,n)
#define forinb(i,arr) forib(i,arr.size())
using namespace std;
#define into(x) cin >> x;
typedef long long lol;
typedef vector<int> veci;
typedef vector<lol> vecl;
typedef pair<lol, lol> point;
typedef pair<int, lol> pointi;
typedef pair<lol, point> poing;
typedef pair<point, lol> poinf;
typedef pair<point, point> poin;
typedef long double ldb;
typedef pair<ldb, ldb> pldb;
#define deft(t,x) t x; into(x)
#define def(x) lol x; into(x)
#define logn 7
#define mod %1000000007
#define maxi 1000000007
#define lmaxi 3000000000000000007
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define con continue;
#define br break;
//#include "cave.h"
#include "nice_lines.h"
map<int, ldb> sofar;
const int x = 20001;
bool online(int x_1, ldb y_1, int x_2, ldb y_2, int x_3, ldb y_3) {
	return abs((y_2 - y_1) / (x_2 - x_1) - (y_3 - y_2) / (x_3 - x_2)) <= 0.000000000001;
}
bool online2(int y) {
	auto it = sofar.find(y);
	auto itt = it;
	itt++;
	auto ittt = itt;
	ittt++;
	return (online(ittt->ff, ittt->ss, itt->ff, itt->ss, it->ff, it->ss));
}
bool turningpoint(int y) {
	auto it = sofar.find(y);
	auto itt = it;
	itt--;
	auto ittt = itt;
	ittt--;
	if (!online(ittt->ff, ittt->ss, itt->ff, itt->ss, it->ff, it->ss)) {
		return false;
	}
	itt++;
	itt++;
	ittt = itt;
	ittt++;
	if (!online(ittt->ff, ittt->ss, itt->ff, itt->ss, it->ff, it->ss)) {
		return false;
	}
	it--;
	if (online(ittt->ff, ittt->ss, itt->ff, itt->ss, it->ff, it->ss)) {
		return false;
	}
	return true;
}
int meetpoint(int x) {
	auto it = sofar.find(x);
	ldb y = it->ss;
	it++;
	int x1 = it->ff;
	ldb y1 = it->ss;
	it++;
	int x2 = it->ff;
	ldb y2 = it->ss;
	it++;
	int x3 = it->ff;
	ldb y3 = it->ss;
	int low = x1+1, high = x2-1;
	while (low < high) {
		int mid = (low + high) / 2;
		if ((low + high) < 0) {
			mid = (low + high - 1) / 2;
		}
		ldb yy = y + ((y1 - y) / (x1 - x)) * (mid - x);
		ldb yyy = y3 + ((y2 - y3) / (x2 - x3)) * (mid - x3);
		if (yy <= yyy + 0.00000001) {
			high = mid;
		}
		else {
			low = mid + 1;
		}
	}
	return low;
}

void solve(int subtask_id, int N) {

	veci found;

	sofar[2*(-210000000)] = query(x, -210000000);
	sofar[2 * (100 - 210000000)] = query(x, 100 - 210000000);
	sofar[2 * (200 - 210000000)] = query(x, 200 - 210000000);
	sofar[2 * 210000000] = query(x, 210000000);
	sofar[2 * (100 + 210000000)] = query(x, 100 + 210000000);
	sofar[2 * (200 + 210000000)] = query(x, 200 + 210000000);
	auto it = sofar.find(2*(200 - 210000000));
	while (found.size() < N) {
		int y = it->ff;
		if (turningpoint(y)) {
			found.push_back(y);
			it++;
			con
		}
		if (online2(y)) {
			it++;
			con
		}
		auto itt = it;
		itt--;
		int y1 = itt->ff;
		if (online2(y1)) {
			it++;
			con
		}
		int cur = meetpoint(y1);
		if (sofar.find(cur) == sofar.end()) {
			sofar[cur] = query(x, cur/2.0);
		}
		else {
			sofar[y - 1] = query(x, (y - 1)/2.0);
			sofar[y + 1] = query(x, (y + 1)/2.0);
			sofar[y + 2] = query(x, (y + 2) / 2.0);
		}
		it = sofar.find(y);
	}
	veci a, b;
	fori(i, N) {
		found[i] /= 2;
		if (found[i] >= 0) {
			int aa = found[i] / x;
			int bb = found[i] % x;
			if (bb > 10000) {
				bb -= x;
				aa += 1;
			}
			a.push_back(aa);
			b.push_back(bb);
		}
		else {
			int aa = (found[i] - x + 1) / x;
			int bb = found[i] - aa * x;
			if (bb > 10000) {
				bb -= x;
				aa++;
			}
			a.push_back(aa);
			b.push_back(bb);
		}
	}
	the_lines_are(a, b);
}

Compilation message

nicelines.cpp: In function 'void solve(int, int)':
nicelines.cpp:129:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |  while (found.size() < N) {
      |         ~~~~~~~~~~~~~^~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 296 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 300 KB Output is correct
2 Correct 7 ms 320 KB Output is correct
3 Correct 5 ms 328 KB Output is correct
4 Correct 8 ms 320 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 3 ms 200 KB Output is correct
4 Correct 3 ms 200 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 300 KB Output is correct
2 Correct 7 ms 320 KB Output is correct
3 Correct 5 ms 328 KB Output is correct
4 Correct 8 ms 320 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 2 ms 200 KB Output is correct
7 Correct 3 ms 200 KB Output is correct
8 Correct 3 ms 200 KB Output is correct
9 Correct 6 ms 328 KB Output is correct
10 Correct 7 ms 324 KB Output is correct
11 Correct 7 ms 200 KB Output is correct
12 Correct 6 ms 316 KB Output is correct