QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523289#8795. Mysterious Sequencesroid_03#WA 0ms4004kbC++2010.8kb2024-08-18 02:26:252024-08-18 02:26:26

Judging History

你现在查看的是最新测评结果

  • [2024-08-18 02:26:26]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4004kb
  • [2024-08-18 02:26:25]
  • 提交

answer


#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T>using ind_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>using ind_mset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

typedef unsigned long long ull;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpll;
typedef vector<vl> vll;
template<class T> using maxpq = priority_queue<T>;
template<class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vec1 = vector<T>;
template<class T> using vec2 = vector<vector<T>>;
template<class T> using vec3 = vector<vector<vector<T>>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i,b,a)  for(ll i =((b)-1);i>=(a);i--)
#define mem(a,x)   memset(a,x,sizeof(a))
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
#define rall(v) (v).rbegin(),(v).rend()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fbo(a) find_by_order(a) //will give a-th largest element
#define ook(a) order_of_key(a) //will give no. of elements strictly lesser than a
#define sz(x) ((int)(x).size())
#define nzl(x) __builtin_clzll(x)
#define nzr(x) __builtin_ctzll(x)
#define setbits(x) __builtin_popcountll(x)
#define setbitsParity(x) __builtin_parityll(x) // 1 -> odd else 0 if even
#define umap unordered_map
#define uset unordered_set
#define nl "\n"
#define PI atan(1)*4
#define E 2.71828
#define yes {cout << "Yes" << endl; return;}
#define no {cout << "No" << endl; return;}
#define YES {cout << "Yes" << endl;}
#define NO {cout << "No" << endl;}
#define nyet {cout<<"-1"<<endl;return;}
#define mxe(v)  (*max_element(v.begin(),v.end()))
#define mne(v)  (*min_element(v.begin(),v.end()))
#define unq(v)  v.resize(distance(v.begin(), unique(v.begin(), v.end())));
#define ub upper_bound
#define lb lower_bound
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
  sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
#define outt(a) \
	  FOR(i,1,sz(a))            \
	  cout << a[i] << " "; \
	  cout << endl;
#define inn(a) \
	  FOR(i,1,sz(a))            \
	  cin>>a[i];
#define FAST_AF_BOI                \
	ios_base ::sync_with_stdio(0); \
	cin.tie(0);               \
	cout.tie(0);

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
	  x += 0x9e3779b97f4a7c15;//abk
	  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
	  x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
	  return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
	  static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
	  return splitmix64(x + FIXED_RANDOM);
  }
};
typedef gp_hash_table<long long,long long,custom_hash> fast_map;
typedef unordered_map<long long,long long,custom_hash> safe_map;

// ================================== i/o module ==================================
template <class T> void _print(T x){cerr<<x;};
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void read(T &x){x=0;int f=0;char ch=getchar();while(ch<'0' || ch>'9')f|=(ch=='-'),ch=getchar();while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();x=f? -x:x;return ;}
template<typename typC,typename typD> istream &operator>>(istream &cin,pair<typC,typD> &a) { return cin>>a.first>>a.second; }
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const pair<typC,typD> &a) { return cout<<a.first<<' '<<a.second; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const vector<pair<typC,typD>> &a) { for (auto &x:a) cout<<x<<'\n'; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
template <class T> inline vector<T>& operator--(vector<T>& v) { for(auto &x:v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { for(auto &x:v) ++x; return v; }
template <class T> inline vector<T>& operator^=(vector<T>& v,int y) { for(auto &x:v) x^=y; return v; }
inline string& operator^=(string& s,int y) { for(auto &x:s)x=((x-'0')^y)+'0' ; return s; }

void dgb_out () { cerr << endl; }
template < typename Head, typename... Tail >
void dgb_out ( Head H, Tail... T) { cerr <<' ' << H; dgb_out (T...); }
#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dgb_out(__VA_ARGS__) 
#else
#define dbg(...)
#endif

// ================================================================================

//`````````````````````````````````````````````IMP FUNCTIONS``````````````````````````````````````````````````````
ll ceil(ll a,ll b){return (a+b-1)/b;}
int log_2(ull i){return i?nzl(1)-nzl(i):-1;}
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll bin_expo(ll a, ll b, ll mod) {ll res = 1;a%=mod;if(a==0)return 0;while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
ll bin_mul(ll a, ll b, ll mod) {ll res = 0; while (b > 0) {if (b & 1)res = (res + a) % mod; a = (a + a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return bin_expo(a, b - 2, b);}
ll ncr(ll n, ll r, ll m, ll *fact, ll *ifact) {if(n<r)return 0;ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r];if(n < r) return 0;if(n == r || r == 0) return 1;if(r<0) return 0; return (((val1 * val2) % m) * val3) % m;}
void google(int t) {cout << "Case #" << t << ": ";}
vl sieve(int n) {int*arr = new int[n + 1](); vl vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i*i <= n; i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
ll large_expo(ll a,ll b,ll c,ll m) {return bin_expo(a,bin_expo(b,c,phin(m)),m);} //(a^b^c)%M 
ll large_expo_prime(ll a,ll b,ll c,ll m) {return bin_expo(a,bin_expo(b,c,m-1),m);} //(a^b^c)%M when m is prime
template<class T>vector<T> prefixSum(vector<T> v, bool flag){vector<T> ans;T sum = 0;if (flag){for (auto &e : v){sum += e;ans.eb(sum);}}else{ans.pb(0);REP(i, v.size(), 0){sum += v[i];ans.eb(sum);}reverse(all(ans));}return ans;}
ll ffs(ll n){if(n==0)return -1;return log2(n & -n);}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll uid(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 
//````````````````````````````````````````````````````````````````````````````````````````````````````````````

const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll N = 5e4 + 10;
const ll mod1 = (1e9 + 7);
const ll mod2 = (998244353);

/*
Self notes cause I need it :
1. dumbfk read the question properly ... I m fed up with this lack of presence of mind
2. dont assume that something is given in question ,like the input is sorted or stuff
   if some step needs the input to be sorted , either check question or sort , dont assume
3. in case you have less time to debug : 
	Common errors :
	  -> Wrote wrong variable names at places cause ur stupid	
	 -> For debugging u hard coded small values and submitted that solution right away
*/

#define int long long

void transcendent(int tc)
{
	ld a, b;
	int n; cin >> a >> b >> n;
	vec1<ld> x(n);
	cin >> x[0] >> x[n - 1];
	ld lo = -100, hi = 100;
	auto calc = [&] (ld p1, ld p2) {
		return a * p1 + b * p2;
	};
	auto upd = [&] (vec1<ld> &tmp) {
		FOR(i, 2, n) tmp[i] = calc(tmp[i - 1], tmp[i - 2]);
	};
	auto check = [&] (ld m) {
		vec1<ld> tmp(n);
		tmp[0] = x[0];
		tmp[1] = m;
		upd(tmp);
		return tmp.back() <= x.back();
	};
	FOR(_, 0, 100) {
		ld m = (hi + lo) / 2;
		if(check(m)) lo = m; else hi = m;
	}
	x[1] = lo;
	upd(x);
	for(auto &y : x) cout << y << nl;
}

static void read(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
}

int32_t main()
{
	//read();
	FAST_AF_BOI
	 auto begin = std::chrono::high_resolution_clock::now();
	cout << fixed << setprecision(12);
	//cerr << fixed << setprecision(0);
	//clock_t timer;
	//timer = clock();
	//PreComp();
	int test = 1;
	// cin >> test;
	FOR(tc, 1, test + 1)
	{
			//cerr << endl << "----Test:" << tc << "----" <<endl;
			transcendent(tc);
	}
	auto end = std::chrono::high_resolution_clock::now();
	 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
	 //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3876kb

input:

1.0 1.0 10 1 10

output:

1.000000000000
-0.323529411765
0.676470588235
0.352941176471
1.029411764706
1.382352941176
2.411764705882
3.794117647059
6.205882352941
10.000000000000

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

1 1 2 1 100

output:

1.000000000000
100.000000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

1 1 5 50 100

output:

50.000000000000
0.000000000000
50.000000000000
50.000000000000
100.000000000000

result:

ok 5 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

0.25 0.25 10 1 1

output:

1.000000000000
55.875536480687
14.218884120172
17.523605150215
7.935622317597
6.364806866953
3.575107296137
2.484978540773
1.515021459227
1.000000000000

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 4000kb

input:

0.25 0.63 6 93 12

output:

93.000000000000
-14.204807958665
55.038798010334
4.810670488624
35.877110368666
12.000000000000

result:

ok 6 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 3996kb

input:

0.25 0.80 10 5 63

output:

5.000000000000
78.769536183531
23.692384045883
68.938724958296
36.188588476280
64.198127085707
45.000402552451
62.608602306678
51.652472618630
63.000000000000

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

0.25 0.99 3 18 30

output:

18.000000000000
48.720000000000
30.000000000000

result:

ok 3 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

0.28 0.64 9 6 10

output:

6.000000000000
20.950403348508
9.706112937582
16.125969765568
10.727183814412
13.324232117999
10.596182634263
11.494439693113
10.000000000000

result:

ok 9 numbers

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3916kb

input:

0.31 0.40 7 10 49

output:

10.000000000000
100.000000000000
35.000000000000
50.850000000000
29.763500000000
29.566685000000
21.071072350000

result:

wrong answer 2nd numbers differ - expected: '240.1150640', found: '100.0000000', error = '0.5835330'