oj.uz

Submission #150050

# Submission time Handle Problem Language Result Execution time Memory
150050 2019-09-01T07:37:31 Z お前はもう死んでいる(#3784, kuroni, nvmdava, tfg) On the Grid (FXCUP4_grid) C++17
12 / 100
 8 ms 384 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 256 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Incorrect 8 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Halted 0 ms 0 KB -
4 Correct 6 ms 344 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Incorrect 8 ms 384 KB Output isn't correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct