oj.uz

Submission #845371

# Submission time Handle Problem Language Result Execution time Memory
845371 2023-09-06T13:22:25 Z Piokemon Cheerleaders (info1cup20_cheerleaders) C++17
26 / 100
 2000 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)1e6+9];
vector<int> stare[(int)1e6+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 5 ms 25180 KB Correct!
2 Correct 6 ms 25264 KB Correct!
3 Correct 5 ms 25176 KB Correct!
4 Correct 7 ms 25180 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25432 KB Correct!
2 Correct 17 ms 26672 KB Correct!
3 Correct 27 ms 26536 KB Correct!
4 Correct 28 ms 26460 KB Correct!

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 548324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 638 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 624 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -