Submission #1175928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175928		Zero_OP	Memory 2 (JOI16_memory2)	C++20	0 / 100	1 ms	328 KiB

memory2

#include "Memory2_lib.h"
#include <bits/stdc++.h>

using namespace std;

namespace{
	
}

void Solve(int T, int N){
	if(N == 1){
		Answer(0, 1, 1);
		return;
	}

	if(N == 2){
		for(int i = 0; i < 4; ++i){
			for(int j = i+1; j < 4; ++j){
				if(Flip(i, j) == 1){
					Answer(i, j, 1);
					
					int x = -1, y = -1;
					for(int k = 0; k < 4; ++k){
						if(k != i && k != j){
							if(x == -1) x = k;
							else y = k;
						}
					}

					Answer(x, y, 0);
					return;
				}
			}
		}
		assert(false);
		return;
	}

	int a = 0, b = 1, cur = Flip(0, 1);

	for(int i = 2; i < 2 * N; ++i){
		int ai = Flip(a, i);
		int bi = Flip(b, i);
		
		int nw = max(ai, bi);
		if(cur < nw){
			cur =  nw;
			if(ai > bi) b = i;
			else a = i;
		}
	}

	// cout << cur << ' ' << a << ' ' << b << '\n';

	vector<int> last = {a};
	vector<int> answer(2 * N, -1);
	for(int i = 0; i < 2 * N; ++i) if(i != a){
		int ai = Flip(a, i);
		if(ai < cur){
			answer[i] = ai;
		} else{
			last.push_back(i);
		}
	}

	// cout << (int)last.size() << '\n';
	// for(int i = 0; i < (int)last.size(); ++i) cout << last[i] << ' '; cout << '\n';

	if((int)last.size() == 2){
		answer[last[0]] = N-1;
		answer[last[1]] = N-1;
	} else{
		assert((int)last.size() == 4);
		for(int i = 0; i < 4; ++i){
			for(int j = i+1; j < 4; ++j){
				if(Flip(last[i], last[j]) == N-1){
					// cout << last[i] << ' ' << last[j] << " : N-1\n";
					answer[last[i]] = N-1;
					answer[last[j]] = N-1;

					int x = -1, y = -1;
					for(int k = 0; k < 4; ++k){
						if(k != i && k != j){
							// cout << "fl : " << k << '\n';
							if(x == -1) x = k;
							else y = k;
						}
					}

					// cout << last[x] << ' ' << last[y] << '\n';

					answer[last[x]] = N-2;
					answer[last[y]] = N-2;
					break;
				}
			}
		}
	}

	vector<pair<int, int>> position(N, make_pair(-1, -1));
	// for(int i = 0; i < 2 * N; ++i) cout << answer[i] << ' '; cout << '\n';
	// return;
	for(int i = 0; i < 2 * N; ++i){
		assert(answer[i] != -1);
		if(position[answer[i]].first == -1) position[answer[i]].first = i;
		else {
			assert(position[answer[i]].second == -1);
			position[answer[i]].second = i;
		}
	}

	for(int i = 0; i < N; ++i){
		Answer(position[i].first, position[i].second, i);
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 50
• Subtask 3: 0 / 40