QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#696631 | #5417. Chat Program | yaLen | WA | 92ms | 26832kb | C++14 | 2.0kb | 2024-10-31 23:57:24 | 2024-10-31 23:57:24 |
Judging History
answer
#include <bits/stdc++.h>
#define KE ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
#define int long long
#define flt(x) cout << fixed << setprecision(x);
#define all(x) (x).begin(), (x).end()
#define bcount(t) __builtin_popcount(t)
#define Mod(x,m) (((x) % m + m) % m)
#define flip(x) reverse(x)
#define lowbit(x) (x&(-x))
#define bemax(x,y) x = max(x, y)
#define pb push_back
#define elif else if
#define endl '\n'
#define AA cerr << "AA" << endl;
#define __ << " " <<
const int N = 1e6 + 10;
const int inf = 1e18;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
int n,k,m,c,d;
vector<int> a(N);
int maxn;
bool check(int x){
vector<int>tag(N);
vector<int>f(N);
int res=0;
int lst = c + (m - 1) * d;
for(int i = 1; i <= n; i++){
if(a[i] >= x){
res++;
tag[i] = 1;
if(res >= k) return true;
}
}
for(int i = 1; i <= m; i++){
if(tag[i] == 1) continue;
if(a[i] + c + (i - 1) * d >= x){
f[m]++;
if(a[i] + c >= x){
f[i + m]--;
}else{
//a[i] + c + p * d < x
int p = (x - c - a[i]);
if(p % d == 0) p = p / d - 1;
else p = p / d;
int det = i - p;
f[m + det]--;
}
}
}
for(int i = m + 1; i <= n; i++){
if(tag[i] == 1) continue;
if(a[i] + lst >= x){
f[i]++;
if(a[i] + c >= x)
f[i + m]--;
else{
int p = (x - c - a[i]);
if(p % d == 0) p = p / d - 1;
else p = p / d;
int det = m - p;
f[i + det]--;
}
}
}
for(int i = m; i <= n; i++){
res += f[i];
if(res >= k){
return 1;
}
}
return false;
}
void solve(){
cin >> n >> k >> m >> c >> d;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int l = 0, r = 1e18;
maxn = c + (m - 1) * d;
while(l < r){
int mid = (l + r + 1) / 2;
if(check(mid))
{
l = mid;
}
else r = mid - 1;
}
cout << l << endl;
}
signed main(){
KE;
int T = 1;
// cin >> T;
// flt(3);
while(T--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 35ms
memory: 26604kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 35ms
memory: 26764kb
input:
7 3 2 4 0 1 9 1 9 8 1 0
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: 0
Accepted
time: 39ms
memory: 26820kb
input:
8 3 5 0 0 2 0 2 2 1 2 1 8
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 88ms
memory: 26676kb
input:
200000 200000 100000 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 88ms
memory: 26584kb
input:
200000 1 100000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
100001000000000
result:
ok 1 number(s): "100001000000000"
Test #6:
score: 0
Accepted
time: 71ms
memory: 26672kb
input:
200000 1 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
200001000000000
result:
ok 1 number(s): "200001000000000"
Test #7:
score: 0
Accepted
time: 92ms
memory: 26608kb
input:
200000 24420 17993 881138881 700368758 231187558 519018952 260661004 740633836 931672020 155904999 647179942 13217847 779799803 382810661 242588977 708308843 309853544 225488875 389115097 588643904 644409212 704920939 231829287 39891424 881158891 341251089 486868469 808002305 629160633 317239613 771...
output:
964474978
result:
ok 1 number(s): "964474978"
Test #8:
score: -100
Wrong Answer
time: 91ms
memory: 26832kb
input:
200000 31878 34175 753689504 94554240 764252685 385025201 185233994 886343186 532991571 477855721 681289648 908112797 112162074 199451201 408329780 674092805 896613552 521026518 597166827 166901445 503106595 958954753 464273450 431481790 32269637 998211679 557906218 821269178 46577165 394469258 5350...
output:
219007886645
result:
wrong answer 1st numbers differ - expected: '218913332405', found: '219007886645'