oj.uz

Submission #857970

# Submission time Handle Problem Language Result Execution time Memory
857970 2023-10-07T08:14:21 Z lovrot The Collection Game (BOI21_swaps) C++17
0 / 100
 1 ms 504 KB 
#include "swaps.h"
#include <cstdio> 
#include <algorithm> 
#include <vector> 

#define EB emplace_back
#define X first
#define Y second

using namespace std;

typedef pair<int, int> pii;

const int LOG = 9;
const int N = 1 << LOG;
const bool DEBUG = 0;

int n;

vector<pii> G;
vector<int> ANS;

void _schedule(int a, int b) {
	G.EB(make_pair(a, b));
	if(DEBUG) printf("? %d[%d] %d[%d]\n", ANS[a], a, ANS[b], b);
	schedule(ANS[a], ANS[b]);
}

void _visit() {
	vector<int> RES = visit(); 
	for(int i = 0; i < RES.size(); ++i) 
		if(!RES[i]) {
			swap(ANS[G[i].X], ANS[G[i].Y]);
			if(DEBUG) printf("<> %d %d\n", ANS[G[i].X], ANS[G[i].Y]);
		}
	G.clear();
}

void solve(int siz, int v) {
	n = siz;
	for(int i = 0; i < n; ++i) ANS.EB(i + 1);
	for(int i = 2; 2 * n > i; i <<= 1) 
		for(int j = i >> 1; j; j >>= 1) {
			for(int k = 0; k < n; ++k) {	
				int l = k ^ j;
				if(l > k && l < n) {
					if(k & i) _schedule(l, k);
					else _schedule(k, l);
				}
			}
			_visit();
		}
	if(DEBUG) for(int i = 0; i < n; ++i) printf("%d%c", ANS[i], " \n"[i == n - 1]);
	answer(ANS);
}

/*
// TODO implement this function
schedule(1, 2);
std::vector<int> v = visit();
if (v[0] == 1)
	answer({1, 2, 3, 4});
else
	answer({2, 1, 3, 4});
*/

Compilation message

swaps.cpp: In function 'void _visit()':
swaps.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < RES.size(); ++i)
      |                 ~~^~~~~~~~~~~~

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3-1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 504 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 504 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not correct
2 Halted 0 ms 0 KB -