QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300899#5044. HappinessSaanteyeWA 151ms3600kbC++174.8kb2024-01-08 23:49:242024-01-08 23:49:25

Judging History

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

  • [2024-01-08 23:49:25]
  • 评测
  • 测评结果:WA
  • 用时:151ms
  • 内存:3600kb
  • [2024-01-08 23:49:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> PII;

//#define p first
//#define d second

void solve(){
    int n; cin >> n;
    vector<string> s(n);
    getchar();
    for (int i = 0; i < n; i++) {
        getline(cin,s[i]);
    }
    vector<vector<int>> sv(n, vector<int> (10));
    vector<vector<int>> pl(n, vector<int> (10));
    vector<int> ac(n),ple(n);

    for (int i = 0; i < n; i++) {
        int tim = 0,fs = -1, cnt = 0;
        for (auto c:s[i]) {
            if (c == '\n') continue;
            else if (c == ' ') fs = 0;
            else if (c >= '0' && c <= '9') {
                if (fs != -1) fs = fs * 10 + c - '0';
                else tim = tim * 10 + c - '0';
            }
            else if (c == ',') {
                sv[i][cnt] = tim; pl[i][cnt] = fs;
                if (fs == -1) sv[i][cnt] = 1e18;
                cnt++; tim = 0; fs = -1;
            }
        }
        sv[i][cnt] = tim; pl[i][cnt] = fs;
        if (fs == -1) sv[i][cnt] = 1e18;
    }
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < 10; j++) {
//            if (pl[i][j] == -1) cout << "- ";
//            else
//            cout << pl[i][j] << ' ';
//        }
//        cout << '\n';
//    }
//for (int i = 0; i < n; i++)
//    cout << sv[i][0] << '\n';
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 10; j++)
            if (sv[i][j] != 1e18)
                ac[i]++, ple[i] = pl[i][j] * 20;

    //mi,mx,fb
    int mi = 1e18, mx = -1e18;
    vector<int> fb(10,1e18);
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < 10; j++) {
            if (sv[i][j] == 1e18) continue;
            fb[j] = min(fb[j],sv[i][j]);
            mi = min(mi, sv[i][j]);
            mx = max(mx, sv[i][j]);
        }
        sort(sv[i].begin(), sv[i].end());
    }

    vector<int> rk(n),rrk(n);
    for (int i = 0; i < n; i++) rk[i] = i;
    sort(rk.begin(), rk.end() - 1,[&](int a,int b){
        if (ac[a] != ac[b]) return ac[a] > ac[b];
        if (ple[a] != ple[b]) return ple[a] < ple[b];
        for (int i = 0; i < 10; i++)
            if (sv[a][i] != sv[b][i])
                return sv[a][i] < sv[b][i];
        return false;
    });

    for (int i = 0; i < n; i++) {
        rrk[rk[i]] = i;
    }
//    for (int i = 0; i < 10; i++)
//        cout << fb[i] << ' ';
//    return;
    vector<int> ord(10);
    iota(ord.begin(), ord.end(),0);
    int ans = 0;
    ac[n - 1] = 0; ple[n - 1] = 1e18;
    do {
        int now = 0, hap = 0;
        int ov1 = 0, ove = 0;
        vector<int> svl(10,1e18);
        int rac = 0, rple = 0;
        for (int i = 0; i < 10; i++) {
            if (sv[n - 1][ord[i]] == 1e18) continue;
            int rsv = sv[n - 1][ord[i]] + now;
            now = rsv;
            rple += rsv + pl[n - 1][ord[i]];
            rac += 1;
            if (rsv <= fb[ord[i]]) hap += 800;
            if (rsv <= mi) ov1 = 1;
            if (rsv >= mx) ove = 1;
            svl[i] = rsv;
        }
        if (ov1) hap += 700;
        if (ove) hap += 500;
        int l = -1, r = n;
        while (r - l > 1) {
            int mid = (r + l) >> 1;
            int idx = rrk[mid];
            if (ac[idx] != rac) {
                if (ac[idx] > rac) l = mid;
                else r = mid;
                continue;
            } else if (ple[idx] != rple) {
                if (ple[idx] < rple) l = mid;
                else r = mid;
                continue;
            } else {
                int f = 0;
                for (int i = 0; i < 10; i++)
                    if (sv[idx][i] != svl[i]) {
                        if (sv[idx][i] > svl[i]) r = mid;
                        else l = mid;
                        f = 1;
                        break;
                    }
                if (!f) r = mid;
                continue;
            }
        }
        r += 1;
//        cout << rac << ' ' << rple << '\n';
        hap += 5000 / r;
        if (r <= n / 10) hap += 1200;
        else if (r <= n / 10 * 3) hap += 800;
        else if (r <= n / 10 * 6) hap += 400;
        ans = max(ans, hap);
    } while (next_permutation(ord.begin(),ord.end()));
    cout << ans;
}

//10
//233 1,-,-,7 7,257 4,173 5,117 1,-,-,85 3
//-,231 0,167 0,257 7,-,-,122 4,283 0,215 4,-
//41 1,-,290 8,-,-,-,-,246 7,120 3,184 9
//142 8,243 7,69 0,-,41 9,-,279 1,264 4,-,74 9
//53 8,-,187 9,60 1,48 8,99 10,-,-,55 7,259 5
//250 0,-,-,-,166 0,16 3,-,82 4,73 0,184 3
//-,-,-,-,105 3,-,-,-,152 4,-
//-,84 5,98 8,-,120 8,241 3,94 1,-,28 7,109 8
//280 6,246 5,58 9,-,-,-,-,-,-,-
//38 10,-,227 10,187 9,182 1,-,203 9,254 7,-,-


signed main(){
//    ios::sync_with_stdio(false);
//    srand(time(0));
    int _ = 1;
    //cin >> _;
    while(_--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 146ms
memory: 3600kb

input:

10
233 1,-,-,7 7,257 4,173 5,117 1,-,-,85 3
-,231 0,167 0,257 7,-,-,122 4,283 0,215 4,-
41 1,-,290 8,-,-,-,-,246 7,120 3,184 9
142 8,243 7,69 0,-,41 9,-,279 1,264 4,-,74 9
53 8,-,187 9,60 1,48 8,99 10,-,-,55 7,259 5
250 0,-,-,-,166 0,16 3,-,82 4,73 0,184 3
-,-,-,-,105 3,-,-,-,152 4,-
-,84 5,98 8,-,1...

output:

1800

result:

ok 1 number(s): "1800"

Test #2:

score: -100
Wrong Answer
time: 151ms
memory: 3600kb

input:

10
15 0,19 10,152 4,45 10,154 7,172 3,168 4,263 1,187 7,24 4
2 3,93 5,113 7,160 0,274 4,128 8,119 0,46 6,50 5,129 2
117 8,190 1,202 1,69 1,64 5,218 0,148 2,156 7,86 2,162 5
209 1,145 0,214 2,99 10,9 1,47 5,235 5,87 3,250 10,285 5
245 0,150 1,237 8,182 7,4 3,38 5,238 6,164 2,259 3,59 6
31 8,44 9,27 6...

output:

1800

result:

wrong answer 1st numbers differ - expected: '1300', found: '1800'