Submission #150050

#	Time	Username	Problem	Language	Result	Execution time	Memory
150050		お前はもう死んでいる (#200)	On the Grid (FXCUP4_grid)	C++17	12 / 100	8 ms	384 KiB

grid

#include "grid.h"

#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <iostream>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());


std::vector<int> known;
std::vector<int> a;
std::vector<int> b;

std::vector<int> gen() {
	std::shuffle(a.begin(), a.end(), rng);
	auto c = a;
	for(int i = 0; i < b.size(); i++) {
		c.push_back(b[i]);
	}
	for(int i = (int) known.size() - 1; i >= 0; i--) {
		c.push_back(known[i]);
	}
	return c;
}

void solve(int n) {
	auto arr = gen();
	int id = PutDisks(arr);
	// for first it's n + id
	//std::cout << "got height " << id << '\n';
	id = id - known.size();
	int size = a.size() + b.size();
	id = size - (id - size) - 1;
	//std::cout << "id is now " << id << '\n';
	assert(0 <= id && id < a.size());
	std::swap(a[id], a.back());
	arr.clear();
	for(int i = 0; i < a.size(); i++) {
		arr.push_back(a[a.size()-i-1]);
	}
	for(int i = 0; i < b.size(); i++) {
		arr.push_back(b[i]);
	}
	for(int i = 0; i < known.size(); i++) {
		arr.push_back(known[known.size()-i-1]);
	}
	int got = PutDisks(arr);
	//std::cout << "trying " << a.back() << ", got " << got << '\n';
	if(PutDisks(arr) == n - known.size() + n - 1) {
		//std::cout << "it's the expected!\n";
		known.push_back(a.back());
		a.pop_back();
	} else {
		//std::cout << "failed with " << a.size() << ", size " << size << '\n';
		b.push_back(a.back());
		a.pop_back();
		solve(n);
	}
}

std::vector<int> SortDisks(int n) {
	for(int i = 0; i < n; i++) {
		a.push_back(i);
	}
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < b.size(); j++) {
			a.push_back(b[j]);
		}
		b.clear();
		solve(n);
	}
	known.push_back(a.back());
	a.pop_back();
	std::vector<int> wtf(n);
	for(int i = 0; i < n; i++) {
		wtf[known[i]] = n-i;
	}
	return wtf;
}

Compilation message (stderr)

grid.cpp: In function 'std::vector<int> gen()':
grid.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < b.size(); i++) {
                 ~~^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from grid.cpp:8:
grid.cpp: In function 'void solve(int)':
grid.cpp:38:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(0 <= id && id < a.size());
                    ~~~^~~~~~~~~~
grid.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++) {
                 ~~^~~~~~~~~~
grid.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < b.size(); i++) {
                 ~~^~~~~~~~~~
grid.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < known.size(); i++) {
                 ~~^~~~~~~~~~~~~~
grid.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(PutDisks(arr) == n - known.size() + n - 1) {
     ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
grid.cpp:50:6: warning: unused variable 'got' [-Wunused-variable]
  int got = PutDisks(arr);
      ^~~
grid.cpp: In function 'std::vector<int> SortDisks(int)':
grid.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < b.size(); j++) {
                  ~~^~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 31
• Subtask 3: 0 / 57