QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#244182#7689. Flipping Cardsycccc319#WA 1ms3544kbC++171.7kb2023-11-08 21:46:262023-11-08 21:46:26

Judging History

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

  • [2023-11-08 21:46:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3544kb
  • [2023-11-08 21:46:26]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int tmp[300010][4];
int n;
int a[300010],b[300010];
bool check(ll x)
{
    for (int i = 1; i <= n; i++) {
        if (a[i] < x) tmp[i][1] = 0;
        else tmp[i][1] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (b[i] < x) tmp[i][2] = 0;
        else tmp[i][2] = 1;
    }
    for (int i = 1; i <= n; i++) {
        tmp[i][3] = tmp[i][2] - tmp[i][1];
    }
    int sum[n + 1];
    sum[1] = tmp[1][3];
    int id = 1;
    int mx{sum[1]}, l = 1, r = 1;
    for (int i = 2; i <= n; i++) {
        sum[i] = sum[i - 1] + tmp[i][3];
        if (sum[i] < sum[id])id = i;
        if (mx < sum[i] - sum[id])l = id, r = i, mx = sum[i] - sum[id];
    }
    int ans[n + 1];
//    for (int i = 1; i <= n; i++) cout<<tmp[i][1]<<" ";
//    cout<<endl;
//    for (int i = 1; i <= n; i++) cout<<tmp[i][2]<<" ";
//    cout<<endl;
//    for (int i = 1; i <= n; i++) cout<<tmp[i][3]<<" ";
//    cout<<endl;
//    cout<<l<<" "<<r<<endl;
    for (int i = 1; i <= l - 1; i++)ans[i] = tmp[i][1];
    for (int i = l; i <= r; i++) ans[i]= tmp[i][1] + tmp[i][3];
    for (int i = r + 1; i <= n; i++) ans[i] = tmp[i][1];
    ll o = 0;
    for (int i = 1; i <= n; i++) if (ans[i] >= 1) o++;

    if(o>=(n+1)/2) return 1;
    else return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
    }
    //test
    ///cout<<check(5)<<endl;
    int L = 0, R = 1e9+10;
    int as = 0;
    while (L < R)
    {
        int x = (R - L >> 1) + L;
        if(check(x))L = x + 1, as = x;
        else R = x;
//        cout<<L<<" "<<R<<endl;
    }
    cout<<L;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3464kb

input:

5
3 6
5 2
4 7
6 4
2 8

output:

6

result:

ok 1 number(s): "6"

Test #2:

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

input:

1
2 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3544kb

input:

1
212055293 384338286

output:

384338287

result:

wrong answer 1st numbers differ - expected: '384338286', found: '384338287'