QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#437658 | #5434. Binary Substrings | chenxinyang2006 | WA | 5ms | 16236kb | C++20 | 3.7kb | 2024-06-09 14:46:12 | 2024-06-09 14:46:13 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n,k;
vector <pii> G[1 << 19];
int cnt,cur[1 << 19],buc[1 << 19];
void add(int u,int v){
// printf("add %d->%d\n",u,v);
++cnt;
G[u].eb(mkp(v,cnt));
G[v].eb(mkp(u,cnt));
}
vector <int> ans;
void dfs(int u){
for(int i = cur[u];i < SZ(G[u]);i = cur[u]){
cur[u] = i + 1;
int v = G[u][i].first;
if(buc[G[u][i].second]) continue;
buc[G[u][i].second] = 1;
dfs(v);
ans.eb(v & 1);
}
}
int nxt[1 << 19][2],val[1 << 19],idx[1 << 19],vis[1 << 19],sz[1 << 19];
int cut,remain;
int test(){
if(remain > sz[cut]) return 0;
int p = cut;
while(remain){
add(p,nxt[p][1]);
p = nxt[p][1];
remain--;
}
return 1;
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&n);
if(n == 1){
printf("0\n");
return 0;
}
if(n == 2){
printf("01\n");
return 0;
}
if(n == 3){
printf("101\n");
return 0;
}
if(n == 4){
printf("1001\n");
return 0;
}
while((1 << (k + 1)) + k <= n) k++;
// printf("k=%d\n",k);
rep(S,0,(1 << k) - 1) add(S >> 1,S & ((1 << (k - 1)) - 1));
rep(u,0,(1 << (k - 1)) - 1) if(cur[u] < SZ(G[u])) dfs(u);
/* printf("semi ans\n");
for(int p:ans) printf("%d",p);
printf("\n");*/
memset(idx,-1,sizeof(idx));
memset(vis,-1,sizeof(vis));
rep(i,0,(1 << k) - 1){
rep(j,0,k - 1) if(ans[(i + j) % (1 << k)]) val[i] |= 1 << (k - 1 - j);
assert(idx[val[i]] == -1);
idx[val[i]] = i;
}
// rep(i,0,(1 << k) - 1) printf("%d ",val[i]);
// printf("\n");
rep(i,0,(1 << k) - 1) nxt[val[i]][0] = val[(i + 1) % (1 << k)];
rep(S,0,(1 << (k + 1)) - 1){
int u = S >> 1;
if((S & ((1 << k) - 1)) != nxt[u][0]) nxt[u][1] = S & ((1 << k) - 1);
}
cut = -1;
rep(u,0,(1 << k) - 1){
if(vis[u] != -1) continue;
int p = u;
while(vis[p] == -1){
vis[p] = 1;
p = nxt[p][1];
sz[u]++;
}
if(cut == -1 || sz[cut] < sz[u]) cut = u;
}
/* rep(u,0,(1 << k) - 1) printf("%d ",nxt[u][0]);
printf("\n");
rep(u,0,(1 << k) - 1) printf("%d ",nxt[u][1]);
printf("\n"); */
// return 0;
rep(u,0,(1 << k) - 1) G[u].clear();
memset(buc,0,sizeof(buc));
memset(cur,0,sizeof(cur));
memset(vis,-1,sizeof(vis));
cnt = 0;
remain = n - k - (1 << k) + 1;
/* printf("remain=%d cut=%d\n",remain,cut);
rep(u,0,(1 << k) - 1) printf("%d ",sz[u]);
printf("\n");*/
int ovo = 0;
rep(u,0,(1 << k) - 1){
if(!sz[u] || u == cut) continue;
ovo |= test();
if(ovo) break;
int p = u;
while(vis[p] == -1){
add(p,nxt[p][1]);
vis[p] = 1;
p = nxt[p][1];
remain--;
}
}
if(!ovo) test();
rep(u,0,(1 << k) - 1) if(u != cut) add(u,nxt[u][0]);
ans.clear();
dfs(nxt[cut][0]);
per(i,k - 1,0) printf("%d",nxt[cut][0] >> i & 1);
reverse(ans.begin(),ans.end());
for(int p:ans) printf("%d",p);
printf("\n");
//接下来视为长度为 k 的串之间的 transfer
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3752kb
input:
2
output:
01
result:
ok meet maximum 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 16168kb
input:
5
output:
11001
result:
ok meet maximum 12
Test #3:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
1
output:
0
result:
ok meet maximum 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
3
output:
101
result:
ok meet maximum 5
Test #5:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
4
output:
1001
result:
ok meet maximum 8
Test #6:
score: 0
Accepted
time: 2ms
memory: 16160kb
input:
6
output:
110100
result:
ok meet maximum 16
Test #7:
score: 0
Accepted
time: 3ms
memory: 16172kb
input:
7
output:
1101001
result:
ok meet maximum 21
Test #8:
score: 0
Accepted
time: 0ms
memory: 16176kb
input:
8
output:
11010001
result:
ok meet maximum 27
Test #9:
score: 0
Accepted
time: 5ms
memory: 16092kb
input:
9
output:
111010001
result:
ok meet maximum 34
Test #10:
score: 0
Accepted
time: 0ms
memory: 16160kb
input:
10
output:
0111010001
result:
ok meet maximum 42
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 16236kb
input:
11
output:
01110101000
result:
wrong answer not meet maximum 48 < 50