QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783265#6255. Conveyor Belts353cerega#WA 0ms3592kbC++143.4kb2024-11-26 05:06:512024-11-26 05:06:51

Judging History

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

  • [2024-11-26 05:06:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3592kb
  • [2024-11-26 05:06:51]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#define X first
#define Y second


const ll mod = 1000000007;
//const ll mod = 998244353;



ll pew(ll a, ll b) {
    ll res = 1;
    while (b>0) {
        if (b&1) res = res*a%mod;
        b >>= 1;
        a = a*a%mod;
    }
    return res;
}




const int N = 111;
vector<int> g[N];
ll dp[N][1<<16][2];
int curmsk[N];
vector<int> was;
vector<pair<int,int>> E;
int k, k2;

void dfs(ll u, ll p) {
    was[u] = 1;
    for (ll v: g[u]) {
        if (v==p) continue;
        if (was[v]==1 and u<v) E.push_back({u,v});
        if (was[v]==0) {
            dfs(v,u);
        }
    }
}

void dfs2(ll u, ll p) {
    was[u] = 1;
    curmsk[u] = 0;
    for (int i=0;i<E.size();i++) {
        if (E[i].X==u or E[i].Y==u) curmsk[u] += (1<<i);
    }
    for (int i=0;i<(1<<k);i++) {
        dp[u][i][0] = dp[u][i][1] = -mod;
    }
    dp[u][0][0] = 0, dp[u][curmsk[u]][1] = 1;
    for (ll v: g[u]) {
        if (v==p) continue;
        if (was[v]==0) {
            dfs2(v,u);
            vector<vector<ll>> nxt(k2,vector<ll>(2,-mod));
            int m1 = curmsk[v];
            int m0 = curmsk[u];
            int nxtmsk = m0^m1;
            for (int l=m0;l>=0;l=(l-1)&m0) {
                int m2 = m1&((1LL<<k)-1-l);
                for (int r=m2;r>=0;r=(r-1)&m2) {
                    for (int b=0;b<2;b++) {
                        for (int b2=0;b2+b<2;b2++) {
                            nxt[(l|r)&nxtmsk][b] = max(nxt[(l|r)&nxtmsk][b],dp[u][l][b]+dp[v][r][b2]);
                        }
                    }
                    if (r==0) break;
                }
                if (l==0) break;
            }
            for (int i=0;i<k2;i++) {
                dp[u][i][0] = nxt[i][0];
                dp[u][i][1] = nxt[i][1];
            }
            curmsk[u] = nxtmsk;
        }
    }
}

const ll K = 31;

void solve() {
    ll A, B;
    cin >> A >> B;
    cin >> A >> B;
    int sz = 1;
    vector<vector<int>> ans(300);
    vector<int> prv(5,0);
    prv[0] = -1, prv[2] = -2, prv[4] = 0;
    int k = 5;
    vector<ll> W = {0, A, A+1, A+B,(1LL<<K)};
    for (int i=K-1;i>=0;i--) {
        vector<int> nxt(k,-3);
        nxt[k-1] = 0;
        nxt[0] = -1;
        nxt[2] = -2;
        if (i==0) nxt[1] = -2, nxt[3] = 0;
        for (int j=0;j<k;j++) {
            if (j==k-1 or prv[j]<0) continue;
            if (j+1<k and W[j]/(1LL<<(i+1))==W[j+1]/(1LL<<(i+1))) continue;
            ll x = W[j]/(1LL<<(i+1))*(1LL<<(i+1));
            int u = sz++, v = sz++;
            ans[prv[j]] = {u,v};
            vector<ll> d(2);
            for (ll b=0;b<2;b++) {
                ll x2 = x+b*(1LL<<i);
                while (d[b]+1<k and x2/(1LL<<i)>=W[d[b]+1]/(1LL<<i)) d[b]++;
                if (nxt[d[b]]==-3) nxt[d[b]] = sz++;
            }
            ans[u] = {0,nxt[d[0]]};
            ans[v] = {nxt[d[1]],0};
        }
        prv = nxt;
    }
    cout << sz << "\n";
    for (int i=0;i<sz;i++) {
        cout << ans[i][0] << " " << ans[i][1] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3592kb

input:

2 3
3 2

output:

99
1 2
0 3
3 0
4 5
0 6
6 0
7 8
0 9
9 0
10 11
0 12
12 0
13 14
0 15
15 0
16 17
0 18
18 0
19 20
0 21
21 0
22 23
0 24
24 0
25 26
0 27
27 0
28 29
0 30
30 0
31 32
0 33
33 0
34 35
0 36
36 0
37 38
0 39
39 0
40 41
0 42
42 0
43 44
0 45
45 0
46 47
0 48
48 0
49 50
0 51
51 0
52 53
0 54
54 0
55 56
0 57
57 0
58 59...

result:

wrong answer Output produces incorrect ratio.