oj.uz

Submission #845375

# Submission time Handle Problem Language Result Execution time Memory
845375 2023-09-06T13:23:24 Z Piokemon Cheerleaders (info1cup20_cheerleaders) C++17
26 / 100
 227 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

map<vector<int>,int> numer;
int ter=1;
pair<int,int> skad[(int)4e7+9];
vector<int> stare[(int)4e7+9];

void dfs(int nr){
	vector<int> a;
	a = stare[nr];
	//cout << nr << ' ';
	//for (int x:a) cout << x << ' ';
	//cout << '\n';
	for (int x=0;x<a.size()/2;x++) swap(a[x],a[x+a.size()/2]);
	if (numer[a] == 0){
		numer[a] = ter++;
		stare[ter-1] = a;
		skad[ter-1] = {nr,1};
		dfs(ter-1);
	}
	a.clear();
	for (int x=0;x<stare[nr].size();x+=2) a.push_back(stare[nr][x]);
	for (int x=1;x<stare[nr].size();x+=2) a.push_back(stare[nr][x]);
	if (numer[a] == 0){
		numer[a] = ter++;
		stare[ter-1] = a;
		skad[ter-1] = {nr,2};
		dfs(ter-1);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,a;
	cin >> n;
	n = (1<<n);
	vector<int> pocz;
	for (int x=0;x<n;x++){
		cin >> a;
		pocz.push_back(a);
	}
	if (n==0){
		cout << "0\n";
		return 0;
	}
	numer[pocz] = ter++;
	stare[1] = pocz;
	dfs(numer[pocz]);
	int inw=1e9,best=0;
	for (int x=1;x<ter;x++){
		pocz = stare[x];
		int temp=0;
		for (int i=0;i<n;i++){
			for (int j=i+1;j<n;j++){
				if (pocz[i]>pocz[j])temp++;
			}
		}
		if (temp<inw){
			inw = temp;
			best= x;
		}
	}
	cout << inw << '\n';
	vector<char> odp;
	while(best!=1){
		//cout << best << '\n';
		odp.push_back('0'+skad[best].second);
		best = skad[best].first;
	}
	for (int x=odp.size()-1;x>=0;x--) cout << odp[x];
}

Compilation message

cheerleaders.cpp: In function 'void dfs(int)':
cheerleaders.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int x=0;x<a.size()/2;x++) swap(a[x],a[x+a.size()/2]);
      |               ~^~~~~~~~~~~
cheerleaders.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int x=0;x<stare[nr].size();x+=2) a.push_back(stare[nr][x]);
      |               ~^~~~~~~~~~~~~~~~~
cheerleaders.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int x=1;x<stare[nr].size();x+=2) a.push_back(stare[nr][x]);
      |               ~^~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 940324 KB Correct!
2 Correct 206 ms 940348 KB Correct!
3 Correct 201 ms 940444 KB Correct!
4 Correct 196 ms 940348 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 940640 KB Correct!
2 Correct 210 ms 941648 KB Correct!
3 Correct 221 ms 941792 KB Correct!
4 Correct 217 ms 941684 KB Correct!

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 210 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 208 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 206 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -