QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783265 | #6255. Conveyor Belts | 353cerega# | WA | 0ms | 3592kb | C++14 | 3.4kb | 2024-11-26 05:06:51 | 2024-11-26 05:06:51 |
Judging History
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.