oj.uz

Submission #398549

# Submission time Handle Problem Language Result Execution time Memory
398549 2021-05-04T13:51:05 Z model_code Nicelines (RMI20_nicelines) C++17
90.3556 / 100
 76 ms 748 KB 
/**
* user:  lendvaj-c30
* fname: Dorijan
* lname: Lendvaj
* task:  NiceLines
* score: 90.35555
* date:  2020-12-04 11:41:12.308338
*/
#include "nice_lines.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
using ll=long long;
using ld=long double;
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
using namespace std;

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

map<pll,bool> bio;
map<pll,ld> res;

ld quer(ll a,ll b)
{
	if (bio[{a,b}]) return res[{a,b}];
	bio[{a,b}]=1;
	return res[{a,b}]=query(a,b);
}

ll di(ll a,ll b)
{
	if (a<0) return (a-b+1)/b;
	else return a/b;
}

void solve(int subtask_id, int N) {
	bio.clear();
	res.clear();
	ll lim=10000;
	if (subtask_id==4) lim=500;
    ll x=lim*2+1,y=(x+2)*lim;
    ld d1=quer(x,-y),d2=quer(x,-y+1);
    ld po=d2-d1;
    ll la=-y;
    vi a,b;
    cout<<fixed<<setprecision(6);
    for (int i=0;i<N;++i)
    {
		ll pom=200;
		while (abs(quer(x,la+pom)-(quer(x,la)+po*pom))<1e-5)
		{
			//cout<<x<<' '<<la<<' '<<la+pom<<' '<<quer(x,la)<<' '<<quer(x,la+pom)<<' '<<po<<endl;
			//cout<<pom<<' '<<query(x,la)+po*pom<<' '<<query(x,la+pom)<<endl;
			po=(quer(x,la+pom)-quer(x,la))/pom;
			pom*=2;
		}
		ll lo=pom/2+1,hi=pom;
		while (lo<hi)
		{
			ll mid=(lo+hi)/2;
			if (abs(quer(x,la+mid)-(quer(x,la)+po*mid))<1e-5) lo=mid+1;
			else hi=mid;
		}
		la=la+lo-1;
		a.pb(di(la+lim,x));
		b.pb(la-a.back()*x);
		d1=quer(x,la);
		d2=quer(x,la+1);
		po=d2-d1;
	}
    the_lines_are(a, b);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
16.9436132534 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 29 ms 548 KB Output is partially correct
2 Partially correct 28 ms 568 KB Output is partially correct
3 Partially correct 34 ms 444 KB Output is partially correct
4 Partially correct 37 ms 484 KB Output is partially correct

Subtask #5
21.6916024178 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 26 ms 384 KB Output is partially correct
2 Partially correct 19 ms 368 KB Output is partially correct
3 Partially correct 25 ms 460 KB Output is partially correct
4 Partially correct 20 ms 388 KB Output is partially correct

Subtask #6
20.7203479893 / 27.0

# Verdict Execution time Memory Grader output
1 Partially correct 29 ms 548 KB Output is partially correct
2 Partially correct 28 ms 568 KB Output is partially correct
3 Partially correct 34 ms 444 KB Output is partially correct
4 Partially correct 37 ms 484 KB Output is partially correct
5 Partially correct 26 ms 384 KB Output is partially correct
6 Partially correct 19 ms 368 KB Output is partially correct
7 Partially correct 25 ms 460 KB Output is partially correct
8 Partially correct 20 ms 388 KB Output is partially correct
9 Partially correct 73 ms 700 KB Output is partially correct
10 Partially correct 76 ms 708 KB Output is partially correct
11 Partially correct 42 ms 748 KB Output is partially correct
12 Partially correct 58 ms 716 KB Output is partially correct