QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#574649 | #9133. Function with Many Maximums | ucup-team3519 | AC ✓ | 24ms | 3684kb | C++20 | 2.2kb | 2024-09-18 23:33:55 | 2024-09-18 23:33:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define cin std::cin
#define cout std::cout
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
//const int MN = 2e5 + 20;
const int INF = 2e9 + 1000;//INF
const LL INFLL = 8e18 + 1000;//INF long long
mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());
const int mod = 998244353;
//模板区域~~~~~~~
// template<class T>
// T ex_gcd(T a, T b, T &x, T &y){
// if(!a){
// x = 0, y = 1;
// return b;
// }
// T ans = ex_gcd(b % a, a, y, x);
// x -= b / a * y;
// return ans;
// }
//模板结束~~~~~~~
void solve() {// n <= 10 solvable
int b; cin >> b;
LL k = 5e5;
cout << k << endl;
LL now = (LL)5e5 * (LL)5e5;
LL dx = 0;
for(int i = 1; i <= b; i++) {
if(i == b) {
// cout << "debug : " << now << endl;
// cout << "res : " << k << endl;
while(k) {
cout << now << " ";
now++, k--;
}
return;
}
cout << now << " ";
k--;
dx = now * 2;
// LL x, y;
// LL g = ex_gcd(3LL, k - 1, x, y);
// assert(g == 1);
// cout << x << "x " << endl;
// x *= now - dx;
// //x -> x >= now
// cout << x << "x " << endl;
// x -= (x - now) / ((k - 1)) * (k - 1);
// if(x < now) x += k - 1;
// cout << x << "x " << endl;
// assert((dx + x * 3 - now) % (k - 1) == 0);
LL x = -now - dx;
x -= (x - (now + 1)) / ((k - 1)) * (k - 1);
if(x <= now) x += k - 1;
cout << x << " ";
dx -= k * (x - now);
dx += 2 * x;
k--;
// cout << dx << "dx" << endl;
assert(dx % k == 0);
now = x + (dx) / k;
assert(now <= 1e12);
}
}
int32_t main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
// cin >> t;
while (t--)
solve();
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 24ms
memory: 3684kb
input:
4
output:
500000 250000000000 250000499982 250002000009 250002499841 250004000042 250004499532 250006000099 250006000100 250006000101 250006000102 250006000103 250006000104 250006000105 250006000106 250006000107 250006000108 250006000109 250006000110 250006000111 250006000112 250006000113 250006000114 2500060...
result:
ok n=500000, max_a=250006500092, max_num=4 >= 4
Test #2:
score: 0
Accepted
time: 16ms
memory: 3680kb
input:
100000
output:
500000 250000000000 250000499982 250002000009 250002499841 250004000042 250004499532 250006000099 250006499055 250008000180 250008498410 250010000285 250010497597 250012000414 250012496616 250014000567 250014495467 250016000744 250016494150 250018000945 250018492665 250020001170 250020491012 2500220...
result:
ok n=500000, max_a=694433724034, max_num=100000 >= 100000
Extra Test:
score: 0
Extra Test Passed