oj.uz

Submission #288552

# Submission time Handle Problem Language Result Execution time Memory
288552 2020-09-01T15:55:42 Z errorgorn "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 109 ms 29008 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k,t;
string s;

vector<string> dp(int i,int j){
	if (j==1){
		vector<string> v;
		string st;
		rep(x,0,i) st+="0";
		v.push_back(st);
		
		rep(x,0,i){
			int temp=sz(v);
			rep(y,temp,0){
				v.push_back(v[y]);
				v.back()[x]='1';
			}
		}
		
		return v;
	}
	else{
		auto v=dp(i-2,j-2);
		vector<string> res;
		
		int t=sz(v);
		
		int idx;
		rep(x,0,i-2) if (v[0][x]==v.back()[x]) idx=x+2;
		
		rep(x,0,t){
			if (x%2==0) res.push_back("00"+v[x%t]);
			else res.push_back("11"+v[x%t]);
		}
		rep(x,0,t){
			if (x%2==0) res.push_back("01"+v[x%t]);
			else res.push_back("10"+v[x%t]);
			
			res.back()[idx]^=1;
		}
		rep(x,0,t){
			if (x%2==0) res.push_back("11"+v[x%t]);
			else res.push_back("00"+v[x%t]);
		}
		rep(x,0,t){
			if (x%2==0) res.push_back("10"+v[x%t]);
			else res.push_back("01"+v[x%t]);
			
			res.back()[idx]^=1;
		}
		
		
		return res;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k>>t;
	cin>>s;
	
	if (k%2==0){
		cout<<"-1"<<endl;
		return 0;
	}
	
	auto v=dp(n,k);
	
	int idx;
	rep(x,0,sz(v)) if (v[x]==s) idx=x;
	
	cout<<sz(v)<<endl;
	rep(x,0,sz(v)) cout<<v[(x+idx)%sz(v)]<<endl;
	
	rep(x,0,sz(v)){
		string s=v[x],t=v[(x+1)%sz(v)];
		
		int cnt=0;
		rep(x,0,n) if (s[x]!=t[x]) cnt++;
		if (cnt!=k) cout<<s<<" "<<t<<endl;
	}
}

Compilation message

lyuboyn.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > dp(int, int)':
lyuboyn.cpp:65:18: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |    res.back()[idx]^=1;
      |                  ^
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:103:27: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |  rep(x,0,sz(v)) cout<<v[(x+idx)%sz(v)]<<endl;
      |                         ~~^~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Ok

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Ok
2 Correct 0 ms 384 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 1 ms 384 KB Ok
8 Correct 0 ms 384 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 21716 KB Ok
2 Correct 41 ms 10936 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Ok
2 Correct 3 ms 892 KB Ok
3 Correct 47 ms 13028 KB Ok
4 Correct 24 ms 6632 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 512 KB Ok
7 Correct 8 ms 2032 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 28960 KB Ok
2 Correct 99 ms 29004 KB Ok
3 Correct 103 ms 27960 KB Ok
4 Correct 48 ms 13012 KB Ok
5 Correct 46 ms 13036 KB Ok
6 Correct 23 ms 6636 KB Ok
7 Correct 21 ms 5620 KB Ok
8 Correct 8 ms 2032 KB Ok
9 Correct 8 ms 2080 KB Ok
10 Correct 5 ms 1400 KB Ok
11 Correct 1 ms 384 KB Ok
12 Correct 1 ms 384 KB Ok
13 Correct 1 ms 384 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 21716 KB Ok
2 Correct 41 ms 10936 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 0 ms 384 KB Ok
7 Correct 3 ms 892 KB Ok
8 Correct 47 ms 13028 KB Ok
9 Correct 24 ms 6632 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 1 ms 512 KB Ok
12 Correct 8 ms 2032 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 101 ms 28960 KB Ok
15 Correct 99 ms 29004 KB Ok
16 Correct 103 ms 27960 KB Ok
17 Correct 48 ms 13012 KB Ok
18 Correct 46 ms 13036 KB Ok
19 Correct 23 ms 6636 KB Ok
20 Correct 21 ms 5620 KB Ok
21 Correct 8 ms 2032 KB Ok
22 Correct 8 ms 2080 KB Ok
23 Correct 5 ms 1400 KB Ok
24 Correct 1 ms 384 KB Ok
25 Correct 1 ms 384 KB Ok
26 Correct 1 ms 384 KB Ok
27 Correct 109 ms 28956 KB Ok
28 Correct 49 ms 13056 KB Ok
29 Correct 100 ms 28960 KB Ok
30 Correct 4 ms 1224 KB Ok
31 Correct 1 ms 384 KB Ok
32 Correct 2 ms 808 KB Ok
33 Correct 8 ms 2076 KB Ok
34 Correct 0 ms 384 KB Ok
35 Correct 0 ms 384 KB Ok
36 Correct 1 ms 384 KB Ok
37 Correct 1 ms 384 KB Ok
38 Correct 48 ms 12936 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12928 KB Ok
2 Correct 98 ms 28952 KB Ok
3 Correct 98 ms 28960 KB Ok
4 Correct 4 ms 1352 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 8 ms 2076 KB Ok
7 Correct 101 ms 29008 KB Ok
8 Correct 1 ms 384 KB Ok
9 Correct 1 ms 384 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 26 ms 6588 KB Ok
12 Correct 61 ms 12920 KB Ok