QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#109602#1441. Special GameKostlinWA 64ms6448kbC++142.2kb2023-05-29 20:59:232023-05-29 20:59:26

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-29 20:59:26]
  • Judged
  • Verdict: WA
  • Time: 64ms
  • Memory: 6448kb
  • [2023-05-29 20:59:23]
  • Submitted

answer

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define fi first
#define sc second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
#define poly vector<int>
const int N=1005,oo=1e9;
inline int read() {
    int x=0,flag=0;char ch=getchar();
    while(ch<'0'||ch>'9') {flag|=(ch=='-');ch=getchar();}
    while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return flag?-x:x;
}
inline int mx(int x,int y) {return x>y?x:y;}
inline int mn(int x,int y) {return x<y?x:y;}
inline void swp(int &x,int &y) {x^=y^=x^=y;}
inline int as(int x) {return x>0?x:-x;}

int n,a[N],b[N],C[N<<1];
int solve(int op,poly A,poly B) {
    if(A.empty()||B.empty()) return 0;
    if(A[0]>B.back()) return mn(A.size(),B.size());
    if(B[0]>A.back()) return 0;
    C[0]=0;
    for(int&V:A) C[++C[0]]=V;
    for(int&V:B) C[++C[0]]=V;
    sort(C+1,C+C[0]+1);
    for(int&V:A) V=lower_bound(C+1,C+C[0]+1,V)-C;
    for(int&V:B) V=lower_bound(C+1,C+C[0]+1,V)-C;
    if(op==1) {
        int len=A.size(),pos=0;C[0]=lower_bound(B.begin(),B.end(),A[0])-B.begin();
        for(int i=1;i<len;++i) {
            C[i]=lower_bound(B.begin(),B.end(),A[i])-B.begin();
            if(C[i]==B.size()) break;
            if(B[C[i]]-A[i]>=B[C[pos]]-A[pos]) pos=i;
        }
        B.erase(lower_bound(B.begin(),B.end(),A[pos]));
        A.erase(A.begin()+pos);
        return solve(2,A,B);
    } else {
        int len=B.size(),pos=0;C[0]=lower_bound(A.begin(),A.end(),B[0])-A.begin();
        for(int i=1;i<len;++i) {
            C[i]=lower_bound(A.begin(),A.end(),B[i])-A.begin();
            if(C[i]==A.size()) break;
            if(A[C[i]]-B[i]>=A[C[pos]]-B[pos]) pos=i;
        }
        A.erase(lower_bound(A.begin(),A.end(),B[pos]));
        B.erase(B.begin()+pos);
        return solve(1,A,B)+1;
    }
}
int main() {
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i) b[i]=read();
    sort(a+1,a+n+1); sort(b+1,b+n+1);
    poly now1,now2; now1.resize(n);now2.resize(n);
    for(int i=1;i<=n;++i) now1[i-1]=a[i],now2[i-1]=b[i];
    printf("%d\n",solve(1,now1,now2));
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3644kb

input:

3
1 2 5
3 4 6

output:

1

result:

ok "1"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

2
4 3
1 2

output:

2

result:

ok "2"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

1
1
2

output:

0

result:

ok "0"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

9
2 12 10 3 4 7 17 14 16
6 1 13 11 9 15 18 8 5

output:

5

result:

ok "5"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

9
1 3 2 14 15 13 8 6 7
12 11 4 17 9 5 18 10 16

output:

3

result:

ok "3"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

4
2 8 1 7
5 6 3 4

output:

2

result:

ok "2"

Test #7:

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

input:

10
9 17 7 11 14 13 2 3 16 1
20 10 6 15 5 8 4 12 18 19

output:

4

result:

ok "4"

Test #8:

score: 0
Accepted
time: 2ms
memory: 3672kb

input:

10
20 14 10 4 13 6 8 12 18 16
3 19 9 11 17 5 7 1 2 15

output:

6

result:

ok "6"

Test #9:

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

input:

9
4 14 11 12 9 10 8 7 15
2 16 1 13 18 6 17 3 5

output:

5

result:

ok "5"

Test #10:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

10
3 17 13 18 16 20 10 5 1 19
7 6 4 14 2 11 9 8 15 12

output:

6

result:

ok "6"

Test #11:

score: -100
Wrong Answer
time: 64ms
memory: 6448kb

input:

821
37 1527 1243 1615 582 1085 1168 524 333 479 130 719 450 946 940 251 908 1458 729 267 1474 623 625 1002 1407 1297 1585 809 32 712 891 943 1331 82 648 655 1295 515 459 982 1486 691 896 1626 1105 903 1255 1593 1444 494 370 537 258 1196 862 1440 539 928 424 1080 1500 1330 317 906 288 727 735 580 811...

output:

409

result:

wrong answer 1st words differ - expected: '406', found: '409'