QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#523289 | #8795. Mysterious Sequence | sroid_03# | WA | 0ms | 4004kb | C++20 | 10.8kb | 2024-08-18 02:26:25 | 2024-08-18 02:26:26 |
Judging History
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'