QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#591950#8230. SubmissionsAprLsityWA 45ms3864kbC++238.4kb2024-09-26 19:22:262024-09-26 19:22:26

Judging History

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

  • [2024-09-26 19:22:26]
  • 评测
  • 测评结果:WA
  • 用时:45ms
  • 内存:3864kb
  • [2024-09-26 19:22:26]
  • 提交

answer

//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef pair<int, int> pii;
typedef array<int, 3> piii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;

const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353, P = 131;

struct team
{
    ull name;
    int pass, tm;

    friend bool operator< (team a, team b)
    {
        if (a.pass == b.pass)
            return a.tm < b.tm;
        return a.pass > b.pass;
    }
};

struct record
{
    int tm, id;
    char q;
    bool ac;

    friend bool operator< (record a, record b)
    {
        if (a.q != b.q)
            return a.q < b.q;
        if (a.tm != b.tm)
            return a.tm < b.tm;
        return a.id < b.id;
    }
};

int m;
vector<team> t;
vector<ull> ans;
map<ull, vector<record>> rc;
map<ull, string> allteam;
int fstac[26];
bool finish[26];
pii cg[26];
int ac2[26];
int cntac[26];
int lstsub[26];

void init()
{
    ans.clear();
    t.clear();
    rc.clear();
    allteam.clear();
    for (int i = 0; i < 26; i++)
        cntac[i] = ac2[i] = lstsub[i] = 0;
}

void solve()
{
    cin >> m;
    init();
    for (int i = 1; i <= m; i++)
    {
        string s;
        cin >> s;
        ull now = 0;
        for (int j = 0; j < s.size(); j++)
            now = now * P + s[j];
        if (rc.count(now)  == 0)
            allteam[now] = s;
        char q;
        int tm;
        string ac;
        cin >> q >> tm >> ac;
        rc[now].push_back({tm, i, q, (ac == "accepted")});
    }
    int et = 0;
    for (auto [k, v] : rc)
    {
        sort(v.begin(), v.end());
        char now = v[0].q;
        bool ok = false;
        int pass = 0, tm = 0;
        int nowtm = 0;
        for (int i = 0; i < v.size(); i++)
        {
            if (v[i].q != now)
                now = v[i].q, ok = false, nowtm = 0;
            if (ok)
                continue;
            if (v[i].ac)
                ok = true, pass++, tm += v[i].tm + nowtm;
            else
                nowtm += 20;
        }
        t.push_back({k, pass, tm});
        et += pass > 0;
    }
    sort(t.begin(), t.end());
    if (t[0].pass == 0)
        return;
    // cerr << t.size() << endl;
    // for (auto it : t)
    //     cerr << allteam[it.name] << " " << it.pass << " " << it.tm << endl;
    int au = min((et + 9) / 10, 35);
    int newau = au;
    if (t.back().pass == 0)
        newau = min(et / 10 + 1, 35);
    int lowau = 0, cnt = 0, newlowau = 0;
    pii highsc = {0, 0};
    for (int i = 0; i < t.size(); i++)
    {
        if (t[i].pass != highsc.first || t[i].tm != highsc.second)
            highsc = {t[i].pass, t[i].tm}, cnt = i;
        if (cnt < au)
            lowau = i;
        if (cnt < newau)
            newlowau = i;
        if (cnt > au && cnt > newau)
            break;
    }
    // cerr << "lowau: " << lowau << endl;
    pii mncg = {0, 0};
    pii lstmncg = {0, 0};
    bool lowauloss = false;
    for (int ii = 0; ii < t.size(); ii++)
    {
        int i = ii;
        if (t.back().pass == 0)
        {
            if (ii == 0)
                i = t.size() - 1;
            else
                i = ii - 1;
        }
        
        if (i < lowau)
        {
            ans.push_back(t[i].name);
            continue;
        }
        for (int j = 0; j < 26; j++)
            fstac[j] = finish[j] = 0;
        for (auto it : rc[t[i].name])
        {
            int q = it.q - 'A';
            // cerr << i << " " << q << " " << ac2[q] << " " << cntac[q] << endl;
            if (finish[q])
                continue;
            if (i == lowau)
            {
                if (it.ac && cntac[q])
                {
                    finish[q] = true;
                    ac2[q] += it.tm;
                    cntac[q]++;
                    continue;
                }
                if (it.ac)
                {
                    fstac[q] += it.tm;
                    ac2[q] += 20;
                    cntac[q]++;
                    continue;
                }
                if (!cntac[q])
                    fstac[q] += 20;
                ac2[q] += 20;
                continue;
            }
            
            if (it.ac)
            {
                fstac[q] += it.tm, finish[q] = true;
                continue;
            }
            fstac[q] += 20;
            if (i == t.size() - 1)
                lstsub[q] = it.tm;
        }
        if (i == t.size() - 1)
        {
            int mx = 0;
            for (int j = 0; j < 26; j++)
                mx = max(mx, fstac[j] + lstsub[j] - 20);
            lstmncg = {1, mx};
        }
        if (i == lowau)
        {
            ans.push_back(t[i].name);
            if (i + 1 == t.size() || (i > 0 && t[i - 1].pass == t[i].pass && t[i - 1].tm == t[i].tm))
                break;
            for (int j = 0; j < 26; j++)
            {
                pii tmp;
                if (!cntac[j])
                    continue;
                if (cntac[j] > 1)
                    tmp = {0, ac2[j] - fstac[j]};
                else
                    tmp = {-1, -fstac[j]};
                if (tmp.first < mncg.first)
                    mncg = tmp;
                else if (tmp.first == mncg.first)
                    mncg.second = max(mncg.second, tmp.second);
            }
            // cerr << mncg.first << " " << mncg.second << endl;
            // cerr << t[i].tm << endl;
            if (t[i + 1].pass > t[i].pass + mncg.first || (t[i + 1].pass == t[i].pass + mncg.first && t[i + 1].tm <= t[i].tm + mncg.second))
                lowauloss = true;
            continue;
        }
        for (int j = 0; j < 26; j++)
        {
            if (!finish[j])
                fstac[j] = -1;
            finish[j] = false;
            cg[j] = {0, 0};
        }
        for (int j = 0; j < 26; j++)
            finish[j] = false;
        for (int j = 0; j < rc[t[i].name].size(); j++)
        {
            auto it = rc[t[i].name][j];
            int q = it.q - 'A';
            // cerr << q << " " << cg[q].first << " " << cg[q].second << endl;
            if (finish[q])
                continue;
            if (it.ac)
            {
                finish[q] = true;
                continue;
            }
            if (fstac[q] == -1)
                cg[q] = {1, it.tm};
            else
                cg[q] = {0, it.tm - fstac[q]};
            // cerr << q << " " << cg[q].first << " " << cg[q].second << endl;
            finish[q] = true;
        }
        pii mxcg = {0, 0};
        for (int j = 0; j < 26; j++)
        {
            if (mxcg.first == cg[j].first)
                mxcg.second = min(mxcg.second, cg[j].second);
            else if (mxcg.first < cg[j].first)
                mxcg = cg[j];
        }
        bool canau = false;
        // cerr << allteam[t[i].name] << " " << mxcg.first << " " << mxcg.second << endl;
        if (t[i].pass + mxcg.first > t[lowau].pass || (t[i].pass + mxcg.first == t[lowau].pass && t[i].tm + mxcg.second <= t[lowau].tm))
            canau = true;
        // cerr << canau << endl;
        if ((t[i].pass > t[newlowau].pass || (t[i].pass == t[newlowau].pass && t[i].tm <= t[newlowau].tm)) && (t[i].pass > lstmncg.first || (t[i].pass == lstmncg.first && t[i].tm <= lstmncg.second)))
            canau = true;
        // cerr << "i: " << i << endl;
        // cerr << canau << endl;
        if (lowauloss && au == min((et + 8) / 10, 35))
        {
            if (t[i].pass == t[lowau + 1].pass && t[i].tm == t[lowau + 1].tm)
                canau = true;
        }
        // cerr << canau << endl;
        if (t[i].pass == 0)
        {
            if (t[i].pass + mxcg.first > t[newlowau].pass || (t[i].pass + mxcg.first == t[newlowau].pass && t[i].tm + mxcg.second <= t[newlowau].tm))
                canau = true;
        }
        if (canau)
            ans.push_back(t[i].name);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
        cout << ans.size() << endl;
        for (int i = 0; i < ans.size(); i++)
            cout << allteam[ans[i]] << " ";
        cout << endl;
        // cerr << endl;
    }
    return 0;
}

详细

Test #1:

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

input:

2
5
TSxingxing10 G 0 rejected
TSxingxing10 B 83 accepted
aoliaoligeiliao J 98 accepted
TS1 J 118 accepted
TS1 B 263 accepted
12
AllWayTheNorth A 0 rejected
YaoYaoLingXian Y 10 accepted
XuejunXinyoudui1 X 200 rejected
XuejunXinyoudui1 X 200 accepted
LetItRot L 215 accepted
AllWayTheNorth W 250 accept...

output:

2
TS1 TSxingxing10 
4
LetItRot ImYourFan AllWayTheNorth XuejunXinyoudui1 

result:

ok 2 test cases ok. (2 test cases)

Test #2:

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

input:

2
2
jiangly_fan A 1 accepted
jiangly B 23 accepted
3
conqueror_of_tourist A 1 accepted
conqueror_of_tourist A 2 accepted
tourist B 23 accepted

output:

2
jiangly_fan jiangly 
1
conqueror_of_tourist 

result:

ok 2 test cases ok. (2 test cases)

Test #3:

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

input:

2
13
A A 1 accepted
A X 1 accepted
K K 1 rejected
B B 2 accepted
C C 2 accepted
D D 2 accepted
E E 2 accepted
F F 2 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 accepted
K K 2 rejected
12
A A 1 accepted
A X 1 accepted
B B 2 accepted
C C 2 accepted
D D 2 accepted
E E 2 accepted
F F 2 a...

output:

11
K A B C D E F G H I J 
1
A 

result:

ok 2 test cases ok. (2 test cases)

Test #4:

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

input:

2
11
A A 1 accepted
B B 1 accepted
C C 2 accepted
D D 2 accepted
E E 2 accepted
F F 2 accepted
G G 2 accepted
H H 2 accepted
I I 2 accepted
J J 2 accepted
K K 2 accepted
12
A A 1 accepted
A X 1 accepted
K K 1 rejected
B B 2 accepted
C C 2 accepted
D D 2 accepted
E E 2 accepted
F F 2 accepted
G G 2 a...

output:

2
A B 
2
K A 

result:

ok 2 test cases ok. (2 test cases)

Test #5:

score: -100
Wrong Answer
time: 45ms
memory: 3620kb

input:

100000
1
M3JytWoaEXxkACy_mBAQ R 111 accepted
1
sQ O 151 accepted
1
JinbrcS58gNEE5yTSkT B 140 accepted
1
cklwBY V 243 accepted
1
v_o42YmvEKFwy Q 260 rejected
1
ftQVK8S_um22w K 265 accepted
1
_bQBeFeDpYQhvZcLf9l3 Z 147 accepted
1
KvDcEAIDN A 75 rejected
1
H3MUK6 A 101 rejected
1
gxYo_oCFn2J8aIben U 54...

output:

1
M3JytWoaEXxkACy_mBAQ 
1
sQ 
1
JinbrcS58gNEE5yTSkT 
1
cklwBY 
0

1
ftQVK8S_um22w 
1
_bQBeFeDpYQhvZcLf9l3 
0

0

1
gxYo_oCFn2J8aIben 
1
_isnlUGK0ddI 
1
BERcVjyCp 
0

0

1
7njYOapSwvogA 
0

1
y1w3KvxylfxwprRBYw 
0

1
iPo0GDhIF 
0

0

0

1
HsVWeBf6j 
0

0

0

0

1
AIfIfX 
1
EYT72BapastGY9a 
0

0

1
Ua...

result:

wrong answer Integer parameter [name=n] equals to 0, violates the range [1, 100000] (test case 5)