QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#248823#7030. Ultraman vs. Aodzilla and BodzillaLevenWA 86ms7684kbC++142.1kb2023-11-11 22:01:192023-11-11 22:01:20

Judging History

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

  • [2023-11-11 22:01:20]
  • 评测
  • 测评结果:WA
  • 用时:86ms
  • 内存:7684kb
  • [2023-11-11 22:01:19]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M = 5e5 + 5;
int squ[M];

inline int find(int x) {
    return lower_bound(squ + 1, squ + M, x) - squ;
}

inline void Solve() {
    int a, b, A, B;
    cin >> a >> b >> A >> B;
    int ans_a(0), ans_b(0);
    int turn_a = find(a);
    int turn_b = find(b);
    int turn_ab = find(a + b);
    string s1, s2;

    // kill A firstly
    int rest = squ[turn_ab] - squ[turn_a];
    ans_a = turn_a * A + turn_ab * B;
    // cout<<turn_a<<" "<<turn_b<<" "<<rest<<endl;
    if (rest >= b) {
        string t1(turn_a, 'A'), t2(turn_ab - turn_a, 'B');
        s1 = t1 + t2;
    } else {
        // use (squ[turn_a] - a) to fuck b
        int ex = squ[turn_a] - a;
        string t1, t2;
        for (int i = 1; i < ex; i++) t1.push_back('A');
        t1.push_back('B');
        for (int i = ex + 1; i <= turn_a; i++) t1.push_back('A');
        for(int i = turn_a + 1; i <= turn_ab; i++) t2.push_back('B');
        s1 = t1 + t2;
    }

    // kill B firstly
    ans_b = turn_b * B + turn_ab * A;
    // if (rest < a) {
    // use (squ[turn_b] - b) to fuck a
    // try to move 'A's lefter 
    rest = squ[turn_b] - b;
    // cout << rest << endl;
    int sum = 0, len = 0;
    while(1) {
        sum += ++len;
        if (rest - sum <= len) {
            sum -= len--;
            break;
        }
    }
    // cout<<len<<endl;
    for (int i = 1; i <= len; i++) s2.push_back('A');
    for (int i = len + 1; i < rest - sum; i++) s2.push_back('B');
    if(rest - sum + 1 != 1)s2.push_back('A');
    for(int i = rest - sum + 1; i <= turn_b; i++) s2.push_back('B');
    for (int i = turn_b + 1; i <= turn_ab; i++) s2.push_back('A');
    // }
    if(ans_a < ans_b) {
        cout<<ans_a<<" "<<s1<<endl;
        return;
    } else if (ans_b < ans_a) {
        cout<<ans_b<<" "<<s2<<endl;
    } else {
        cout<<ans_a<<" "<<min(s1, s2)<<endl;
    }
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    for (int i = 1; i < M; i++) squ[i] = squ[i - 1] + i;
    while(T--) Solve();
    return 0;   
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7464kb

input:

2
5 15 5 25
5 15 25 5

output:

155 BBBBBA
105 AAABBB

result:

ok 2 cases

Test #2:

score: -100
Wrong Answer
time: 86ms
memory: 7684kb

input:

100000
1 1 1 1
1 1 1 2
1 1 1 3
1 1 1 4
1 1 1 5
1 1 1 6
1 1 1 7
1 1 1 8
1 1 1 9
1 1 1 10
1 1 2 1
1 1 2 2
1 1 2 3
1 1 2 4
1 1 2 5
1 1 2 6
1 1 2 7
1 1 2 8
1 1 2 9
1 1 2 10
1 1 3 1
1 1 3 2
1 1 3 3
1 1 3 4
1 1 3 5
1 1 3 6
1 1 3 7
1 1 3 8
1 1 3 9
1 1 3 10
1 1 4 1
1 1 4 2
1 1 4 3
1 1 4 4
1 1 4 5
1 1 4 6
1 ...

output:

3 AB
4 BA
5 BA
6 BA
7 BA
8 BA
9 BA
10 BA
11 BA
12 BA
4 AB
6 AB
7 BA
8 BA
9 BA
10 BA
11 BA
12 BA
13 BA
14 BA
5 AB
7 AB
9 AB
10 BA
11 BA
12 BA
13 BA
14 BA
15 BA
16 BA
6 AB
8 AB
10 AB
12 AB
13 BA
14 BA
15 BA
16 BA
17 BA
18 BA
7 AB
9 AB
11 AB
13 AB
15 AB
16 BA
17 BA
18 BA
19 BA
20 BA
8 AB
10 AB
12 AB
14...

result:

wrong answer In case 2303 (3 4 1 3), the jury's solution is better.