QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300974#5434. Binary SubstringsOAleksaWA 20ms24404kbC++141.7kb2024-01-09 08:49:172024-01-09 08:49:19

Judging History

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

  • [2024-01-09 08:49:19]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:24404kb
  • [2024-01-09 08:49:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
vector<int> g[N];
int vis[N], id[N], vis2[N];
int sl[N];
vector<int> ord;
void dfs(int v) {
	if (vis[v])
		return;
	vis[v] = 1;
	for (auto u : g[v]) 
		dfs(u);
	ord.push_back(v);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int k = 0;
  while ((1 << (k + 1)) + k <= n)
  	++k;
  if (n == 1) {
  	cout << "0";
  	return 0;
  }
  else if (n == 2) {
  	cout << "01";
  	return 0;
  }
  for (int i = 0;i < (1 << k);i++) {
  	int x = (i * 2) % (1 << k);
  	g[i].push_back(x);
  	g[i].push_back(x + 1);
  }
  dfs(0);
  reverse(ord.begin(), ord.end());
  int sz = ord.size();
  if (n == (1 << k) + k - 1) {
  	for (int i = 0;i < k - 1;i++)
  		cout << 0;
  	for (auto u : ord)
  		cout << (u & 1);
  	return 0;
  }
  for (int i = 0;i < sz;i++) {
  	ord[i] *= 2;
  	if (i < sz - 1)
  		ord[i] |= (ord[i + 1] & 1);
  	vis2[ord[i]] = 1; //postoji
  }
  for (int i = 0;i < sz;i++) 
  	sl[ord[i]] = ord[(i + 1) % sz];
  for (int i = 0;i < (1 << (k + 1));i++) {
  	if (vis2[i])
  		continue;
  	sl[i] = sl[i ^ (1 << k)] ^ 1;
  }
  int t = sz;
  for (int mask = 0;mask < (1 << (k + 1));mask++) {
  	if (vis2[mask])
  		continue;
  	int j = mask;
  	while (!vis2[j]) {
  		t++;
  		vis2[j] = 1;
  		j = sl[j];
  	}
  	swap(sl[mask], sl[mask ^ (1 << k)]);
  	if (t + k > n) {
  		int x = sl[mask];
  		for (int i = k;i > 0;i--) {
  			cout << ((x >> i) & 1);
  		}
  		for (int i = 0;i < n - k;i++) {
  			cout << (x & 1);
  			x = sl[x];
  		}
  		return 0;
  	}
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

01

result:

ok meet maximum 3

Test #2:

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

input:

5

output:

00110

result:

ok meet maximum 12

Test #3:

score: 0
Accepted
time: 2ms
memory: 8528kb

input:

1

output:

0

result:

ok meet maximum 1

Test #4:

score: 0
Accepted
time: 2ms
memory: 11468kb

input:

3

output:

010

result:

ok meet maximum 5

Test #5:

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

input:

4

output:

1001

result:

ok meet maximum 8

Test #6:

score: 0
Accepted
time: 2ms
memory: 12328kb

input:

6

output:

001100

result:

ok meet maximum 16

Test #7:

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

input:

7

output:

1000110

result:

ok meet maximum 21

Test #8:

score: 0
Accepted
time: 2ms
memory: 11720kb

input:

8

output:

10001101

result:

ok meet maximum 27

Test #9:

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

input:

9

output:

110100011

result:

ok meet maximum 34

Test #10:

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

input:

10

output:

0001011100

result:

ok meet maximum 42

Test #11:

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

input:

11

output:

00010111000

result:

ok meet maximum 50

Test #12:

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

input:

12

output:

011100001011

result:

ok meet maximum 59

Test #13:

score: -100
Wrong Answer
time: 20ms
memory: 24404kb

input:

200000

output:

101111111001110011111111101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer not meet maximum 5599502 < 19996962278