QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206871#5161. Last GuessMinhhoWA 1ms6428kbC++207.3kb2023-10-07 23:34:442023-10-07 23:34:45

Judging History

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

  • [2023-10-07 23:34:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6428kb
  • [2023-10-07 23:34:44]
  • 提交

answer

#define taskname "L"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2005, oo = 1e9;
vector<int> adj[maxn];
int cap[30], mn[30], fx[maxn], ban[maxn][30], cur[maxn], d[maxn], ans[maxn], fxl[30];
int tin[maxn], tout[maxn], cnt, n, m, s, t, _s, _t, cell, l;
string ds[maxn], dt[maxn];

struct edge {
    int u, v, de, f, c;
} e[maxn*maxn];

inline void add(int u, int v, int c, int de = 0)
{
    if (c == 0) return;
    if (v == t) assert(u >= cell+1 && u <= cell+l);
    if (u == s) assert(v == _t);
//    if ((u == s || v == t || true) && (c > 0))
//    cerr<<"ADD: "<<u<<" "<<v<<" "<<c<<" "<<de<<"\n";
    adj[u].emplace_back(cnt);
    e[cnt++] = {u, v, de, 0, c};
    tin[v] += de;
    tout[u] += de;
    adj[v].emplace_back(cnt);
    e[cnt++] = {v, u, 0, 0, 0};
}

inline bool BFS(int st = s, int ed = t)
{
    fill(d, d+ed+1, -1);
    d[st] = 0;
    queue<int> q;
    q.emplace(st);
    while (q.size())
    {
        int u = q.front(); q.pop();
        for (int id: adj[u])
        {
            auto [_, v, de, f, c] = e[id];
            if (d[v] == -1 && f < c) d[v] = d[u] + 1, q.emplace(v);
        }
    }
    return d[ed] != -1;
}

int DFS(int u = s, int flow = 1e9)
{
//    cerr<<"CUR: "<<u<<" "<<flow<<"\n";
    if (u == t) return flow;
    for (int &i=cur[u]; i<adj[u].size(); i++)
    {
        int id = adj[u][i];
        auto [_, v, de, f, c] = e[id];
        if (d[v] == d[u] + 1 && f < c)
        {
            int tmp = DFS(v, min(flow, c - f));
            if (tmp)
            {
                e[id].f += tmp;
                e[id^1].f -= tmp;
                return tmp;
            }
        }
    }
    return 0;
}

/**
s = 0
cells: 1 -> cell
letters: cell+1 -> cell+l
_s = cell+l+1;
_t = cell+l+2;
t = cell+l+3
**/
/**
string aa = "lufzobcdioevnkuwizhx", bb = "YYBBBGBBBBBGBBBBBBBB", cc = "vavlabmpqravasaauavj";
**/
inline void comp(string a, string b, string c, int id)
{

    int tp[30], bn[30], dm[30];
    memset(tp, 0, sizeof tp);
    memset(bn, 0x3f3f3f, sizeof bn);
    memset(dm, 0, sizeof dm);
    for (int i=0; i<a.size(); i++)
    {
        if (b[i] != 'B') tp[a[i]-'a']++;
        else bn[a[i]-'a'] = 1;
    }
    for (int i=0; i<26; i++) if (bn[i] == 1) bn[i] = tp[i];
    bool f = 0;
    for (int i=0; i<a.size(); i++)
    {
        dm[c[i]-'a']++;
        if (b[i] == 'G' && a[i] != c[i]) f = 1, cout<<"WA: "<<i<<" NOT MATCH\n";
    }
    for (int i=0; i<26; i++)
    {
        if (dm[i] < tp[i]) f = 1, cout<<"WA: "<<(char)(i+'a')<<" NOT ENOUGH "<<"SHOULD HAVE: "<<tp[i]<<" FOUND: "<<dm[i]<<"\n";
        if (dm[i] > bn[i]) f = 1, cout<<"WA: "<<(char)(i+'a')<<" TOO MANY\n";
    }
    if (f) cout<<"WORD: "<<id<<" "<<dt[id]<<" "<<ds[id]<<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>m>>n;
    memset(fx, -1, sizeof fx);
    memset(ans, -1, sizeof ans);
    for (int i=0; i<26; i++) cap[i] = 1e9;
    int mdem[30], mg[30];
    memset(mdem, 0, sizeof mdem);
    memset(mg, 0, sizeof mg);
    for (int i=1; i<m; i++)
    {
        string s, t;
        cin>>t>>s;
        dt[i] = t;
        ds[i] = s;
        int tmp[30], dem[30], tg[30];
        memset(dem, 0, sizeof dem);
        memset(tmp, 0, sizeof tmp);
        memset(tg, 0, sizeof tg);
        vector<int> bn;
        for (int j=0; j<n; j++)
            if (s[j] == 'G') fx[j] = t[j] - 'a', ans[j] = t[j] - 'a', dem[t[j]-'a']++, tg[t[j]-'a']++;
            else if (s[j] == 'Y') ban[j][t[j]-'a'] = 1, dem[t[j]-'a']++, tmp[t[j]-'a']++;
            else bn.emplace_back(t[j]-'a'), ban[j][t[j]-'a'] = 1;
        for (int j: bn) if (cap[j] == 1e9) cap[j] = dem[j]; else assert(cap[j] == dem[j]);
        for (int j=0; j<26; j++) mn[j] = max(mn[j], tmp[j]), mdem[j] = max(mdem[j], dem[j]), mg[j] = max(mg[j], tg[j]);
    }
    for (int i=0; i<n; i++) if (fx[i] != -1) fxl[fx[i]]++;
    for (int i=0; i<26; i++) if (cap[i] != 1e9) cap[i] -= fxl[i], mn[i] = cap[i]; else mn[i] = mdem[i] - mg[i];
    for (int i=0; i<26; i++) assert(mn[i] <= cap[i]);
//    mn['v'-'a'] = 1;
    if (m == 30 && n == 20)
    for (int i=0; i<26; i++)
    {
        if (mn[i] > 0) cout<<(char)(i+'a')<<" "<<mn[i]<<" "<<cap[i]<<" "<<fxl[i]<<"  \n"[i%8 == 0];
        //assert(mn[i] <= cap[i]);
    }
    /**
    CORRECT: j 1 1000000000 0 l 1 1000000000 0 m 1 1 0 p 1 1 0 q 1 1000000000 0 r 1 1 0 u 1 1 0 v 1 1000000000 2 y 1 1000000000 0
    WRONG:   j 1 1000000000 0 l 1 1000000000 0 m 1 1 0 p 1 1 0 q 1 1000000000 0 r 1 1 0 u 1 1 0 y 1 1000000000 0
    WRONG2:  j 1 1000000000 0 l 1 1000000000 0 m 1 1 0 p 1 1 0 q 1 1000000000 0 r 1 1 0 u 1 1 0 v 1 1000000000 2 y 1 1000000000 0
    **/
    cell = 0;
    vector<int> ve;
    for (int i=0; i<n; i++) if (fx[i] == -1) ve.emplace_back(i);
    cell = ve.size();
    l = 26;
    s = 0;
    _s = cell+l+1;
    _t = _s+1;
    t = _t+1;
//    cerr<<"SS: "<<s<<" "<<t<<"\n";
    int din = 0;
    for (int i=1; i<=cell; i++)
    {
        add(_s, i, 1);
        for (int j=1; j<=26; j++) if (!ban[ve[i-1]][j-1]) add(i, cell+j, 1), din += (j == 25);
    }
    for (int i=1; i<=26; i++) add(cell+i, _t, cap[i-1], mn[i-1]);
    add(_t, _s, oo);
    for (int i=0; i<cnt; i++) e[i].c -= e[i].de;
    for (int i=1; i<t; i++) add(s, i, tin[i]), add(i, t, tout[i]);
//    if (m == 30 && n == 20) cout<<"Y: "<<mn[24]<<" "<<tout[cell+25]<<" "<<din<<"\n";
    int anss = 0;
    while (BFS())
    {
        fill(cur, cur+t+1, 0);
        int x;
        while (x = DFS(s, oo)) anss += x;
    }
    int smn = accumulate(mn, mn+26, 0);
//    assert(anss == smn);
//    cerr<<"LUONG: "<<anss<<"\n";
    for (int i=0; i<cnt; i++)
    {
        auto [u, v, de, f, c] = e[i];
        if (u >= 1 && u <= cell && v >= cell+1 && v <= cell+l)
        {
//            cerr<<"F & C: "<<f<<" "<<c<<"\n";
//            cerr<<"WUT: "<<u<<" "<<v<<" "<<d[u]<<" "<<d[v]<<"\n";
            if (f == c)
                ans[ve[u-1]] = v - (cell+1);//, cerr<<"ANS: "<<ve[u-1]<<" "<<(v-cell-1)<<"\n";
        }
    }
    string res="";
    for (int i=0; i<n; i++) res += (char)(ans[i]+'a');
    string a = "lufzobcdioevnkuwizhx", b = "YYBBBGBBBBBGBBBBBBBB", c = "vajlab````avasaa`a``";
//    comp(a, b, c, 1);
//    if (res[0] == 'v')
//        for (int i=1; i<m; i++)
//        {
//            string aa = dt[i], bb = ds[i], cc = res;
//            comp(aa, bb, cc, i);
//        }
//    for (int i=1; i<m; i++)
//    {
//        for (int j=0; j<n; j++)
//        {
//            if (ds[i][j] == 'G')
//            {
//                if (res[j] != dt[i][j]) cout<<"WA ON TEST: "<<i<<" MUST BE: "<<dt[i][j]<<" AT: "<<j<<" FOUND: "<<res[j]<<"\n";
//            }
//            else
//            {
//                if (res[j] == dt[i][j]) cout<<"WA ON TEST: "<<i<<" MUST NOT BE: "<<dt[i][j]<<" AT: "<<j<<" FOUND: "<<res[j]<<"\n";
//            }
//        }
//    }
    cout<<res;
//    if (res[0] == 'v') for (int i=21; i<m; i++) cout<<"\n"<<ds[i]<<" "<<dt[i];
}
/**
vavlabmpqravasaauavj
7 20
lufzobcdioevnkuwizhx YYBBBGBBBBBGBBBBBBBB
bofouctortorouvpypjs YBBBYBBBYBBBBBYYYBYY
isbkmjdvginytdqdseep BYYBYYBYBBBYBBYBBBBY
fkbdxuovsmemmzykfrzi BBYBBYBYYYBBBBYBBYBB
vidzhkorpdefmkdhhdtz GBBBBBBYYBBBYBBBBBBB
dtecigfkwjyvnqbcoles BBBBBBBBBYYGBYYBBYBY
**/

詳細信息

Test #1:

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

input:

4 5
reply YYGBB
refer BBBGG
puppy YYGBB

output:

upper

result:

ok 

Test #2:

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

input:

2 12
aabbccddeeff GGGYGBYYYBBB

output:

aabdcbe`d```

result:

ok 

Test #3:

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

input:

25 500
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqoqqqqqqqqqqqqqqqqqqqqqqoqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqjq...

output:

abcdefghijklmnoooprstuvwxyz`````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````...

result:

ok 

Test #4:

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

input:

24 500
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvuvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

abcdefghijklmnoppqrstuwxyz``````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````...

result:

ok 

Test #5:

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

input:

23 500
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqgqqqqq...

output:

abcdefggghijklmnoprstuuuvwxyz```````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````...

result:

ok 

Test #6:

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

input:

22 500
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccoccccccccccccccccccccccccccccccccccccccccccccccccfccccccccccccccccccccccccccccccccc...

output:

abbbdefffghijklmnopqrstuvwxyz```````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````...

result:

ok 

Test #7:

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

input:

30 20
azzzzzzzzzzzzzzzzzzz YBBBBBBBBBBBBBBBBBBB
zazzzzzzzzzzzzzzzzzz BGBBBBBBBBBBBBBBBBBB
zzazzzzzzzzzzzzzzzzz BBYBBBBBBBBBBBBBBBBB
zzzazzzzzzzzzzzzzzzz BBBYBBBBBBBBBBBBBBBB
zzzzazzzzzzzzzzzzzzz BBBBGBBBBBBBBBBBBBBB
zzzzzazzzzzzzzzzzzzz BBBBBYBBBBBBBBBBBBBB
zzzzzzazzzzzzzzzzzzz BBBBBBYBBBBBBBBBBBBB
...

output:

j 1 1000000000 0 l 1 1000000000 0 m 1 1 0 p 1 1 0 q 1 1000000000 0 r 1 1 0 u 1 1 0 v 1 1000000000 2 y 1 1000000000 0 vaylabmpqravasaauavj

result:

FAIL Condition failed: "answer.size() == n"