oj.uz

Submission #674820

# Submission time Handle Problem Language Result Execution time Memory
674820 2022-12-26T09:17:49 Z QwertyPi Shuffle (NOI19_shuffle) C++14
19 / 100
 3 ms 724 KB 
#include "shuffle.h"
#include <bits/stdc++.h>

#ifdef ONLINE_JUDGE
#define cout cerr
#endif
using namespace std;

using v2d = vector<vector<int>>;
using v1d = vector<int>;

int N, B, K;
v2d self_suffle(v2d query){
	for(auto& q : query){
		for(auto& i : q){
			i = (i % N + N) % N + 1;
		}
	}
	return shuffle(query);
}

void norm(v2d& v2){
	for(auto& v : v2){
		sort(v.begin(), v.end());
	}
	sort(v2.begin(), v2.end());
}

const int MAXN = 1e4 + 11;
vector<int> G[MAXN];
deque<int> val;
bool vis[MAXN];
int c[MAXN];
void dfs(int v, int pa = -1){
	vis[v] = true; val.push_back(v);
	for(auto i : G[v]){
		if(i != pa && !vis[i]) c[i] = c[v] ^ 1, dfs(i, v);
	}
}

bool is_adj(int u, int v){
	for(auto i : G[u]){
		if(i == v) return true;
	}
	return false;
}

int adj_exc(int u, int v){
	for(auto i : G[u]){
		if(i != v) return i;
	}
	return -1;
}

ostream& operator<< (ostream& out, v2d v){
	out << "Vec2d: " << endl;
	for(auto i : v){
		for(auto ii : i){
			out << ii << ' ';
		}
		out << endl;
	}
	return out << endl;
}

ostream& operator<< (ostream& out, v1d v){
	out << "Vec1d: " << endl;
	for(auto i : v){
		out << i << ' ';
	}
	return out << endl;
}

vector<int> solve(int N, int B, int K, int Q, int ST) {
	::N = N, ::B = B, ::K = K;
	vector<int> ans(N);
	if(K == 2){
		v2d query, res;
		for(int i = 0; i < B; i++){
			query.push_back({i * 2, i * 2 + 1});
		}
		res = self_suffle(query);
		for(auto p : res){
			G[p[0]].push_back(p[1]);
			G[p[1]].push_back(p[0]); 
		}
		query.clear(); 
		for(int i = 0; i < B; i++){
			query.push_back({i * 2, i * 2 - 1});
		}
		res = self_suffle(query);
		for(auto p : res){
			G[p[0]].push_back(p[1]);
			G[p[1]].push_back(p[0]); 
		}
		dfs(1);
		query.clear();
		query.push_back({0, 2});
		query.push_back({1, 3});
		for(int i = 2; i < B; i++){
			query.push_back({i * 2, i * 2 + 1});
		}
		v2d v1 = self_suffle(query);
		
		query.clear();
		query.push_back({0, 2});
		query.push_back({3, 5});
		query.push_back({1, 4});
		for(int i = 3; i < B; i++){
			query.push_back({i * 2, i * 2 + 1});
		}
		v2d v2 = self_suffle(query);
		
		norm(v1), norm(v2);
		v2d s1, s2;
		for(int i = 0; i < B; i++){
			if(c[v1[i][0]] == c[v1[i][1]]) s1.push_back(v1[i]);
			if(c[v2[i][0]] == c[v2[i][1]]) s2.push_back(v2[i]);
		}
		v1d a02;
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				if(s1[i] == s2[j]){
					a02 = s1[i];
					if(s1[!i][0] == s2[!j][0] || s1[!i][1] == s2[!j][0]) ans[3] = s2[!j][0];
					else ans[3] = s2[!j][1];
				}
			}
		}
		if(is_adj(a02[0], ans[3])) ans[2] = a02[0], ans[0] = a02[1];
		else ans[2] = a02[1], ans[0] = a02[0];
		
		ans[1] = adj_exc(ans[2], ans[3]);
		for(int i = 4; i < N; i++){
			ans[i] = adj_exc(ans[i - 1], ans[i - 2]);
		}
	}
	// cout << ans;
	return ans;
}

Subtask #1
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 556 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 724 KB Output is correct

Subtask #5
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -