oj.uz

답안 #288236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
288236 2020-09-01T10:42:02 Z abyyskit Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 3 ms 640 KB 
#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back

int N;
vector<int> P;

vector<string> addreq(int n){
	if (n == 2){
		return {"10"};
	}
	else{
		vector<string> tmp = addreq(n/2);
		vector<string> ans(tmp.size()*2 + n/2);
		string app(n/2, '1');
		string base(n, '0');
	//	cout << "appbase\n";
	//	cout << app << "\n";
	//	cout << base << "\n";
		FOR(i, 0, n/2){
			ans[i] = base;
			ans[i][i] = '1';
		}
		FOR(i, 0, tmp.size()){
			ans[i + n/2] = tmp[i] + app;
		}
		FOR(i, 0, tmp.size()){
			ans[i + n/2 + tmp.size()] = app + tmp[i];
		}
		return ans;
	}
}

void solve (int start, int end, vector<int>& pos){
	//inclusive-exclusive
	string base(N, '1');
	FOR(i, 0, pos.size()){
		base[pos[i]] = '0';
//		cout << pos[i] << "\n";
	}
//	cout << "base: " << base << "\n";
	if (end - start == 2){
//		cout << "base case\n";
		base[pos[0]] = '1';
//		cout << base << "\n";
		if (check_element(base)){
//			cout << "True\n";
			P[pos[0]] = start;
			P[pos[1]] = start + 1;
		}
		else{
//			cout << "False\n";
			P[pos[0]] = start + 1;
			P[pos[1]] = start;
		}
		return;
	}
	vector<int> fi;
	vector<int> se;
	FOR(i, 0, pos.size() - 1){
		base[pos[i]] = '1';
		bool store = check_element(base);
		if (store){
			fi.pb(pos[i]);
		}
		else{
			se.pb(pos[i]);
		}
		base[pos[i]] = '0';
	}
	if (fi.size() == (end - start)/2){
		se.pb(pos.back());
	}
	else{
		fi.pb(pos.back());
	}
	solve(start, start + (end - start)/2, fi);
	solve(start + (end - start)/2, end, se);
}


vector<int> restore_permutation(int n, int w, int r) {
	N = n;
	P.resize(n);
	vector<string> W = addreq(n);
	FOR(i, 0, W.size()){
		//cout << W[i] << "\n";
		add_element(W[i]);
	}
	compile_set();
	//check_element("0");
	vector<int> work(n);
	FOR(i, 0, n){
		work[i] = i;
	}
//	cout << "here\n";
	solve(0, n, work);
//	cout << "here\n";
//	FOR(i, 0, P.size()){
//		cout << P[i] << " ";
//	}
//	cout << "\n";
	return P;
}

Compilation message

messy.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > addreq(int)':
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   26 |   FOR(i, 0, tmp.size()){
      |       ~~~~~~~~~~~~~~~~                 
messy.cpp:26:3: note: in expansion of macro 'FOR'
   26 |   FOR(i, 0, tmp.size()){
      |   ^~~
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   29 |   FOR(i, 0, tmp.size()){
      |       ~~~~~~~~~~~~~~~~                 
messy.cpp:29:3: note: in expansion of macro 'FOR'
   29 |   FOR(i, 0, tmp.size()){
      |   ^~~
messy.cpp: In function 'void solve(int, int, std::vector<int>&)':
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   39 |  FOR(i, 0, pos.size()){
      |      ~~~~~~~~~~~~~~~~                  
messy.cpp:39:2: note: in expansion of macro 'FOR'
   39 |  FOR(i, 0, pos.size()){
      |  ^~~
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   62 |  FOR(i, 0, pos.size() - 1){
      |      ~~~~~~~~~~~~~~~~~~~~              
messy.cpp:62:2: note: in expansion of macro 'FOR'
   62 |  FOR(i, 0, pos.size() - 1){
      |  ^~~
messy.cpp:73:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  if (fi.size() == (end - start)/2){
      |      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   88 |  FOR(i, 0, W.size()){
      |      ~~~~~~~~~~~~~~                    
messy.cpp:88:2: note: in expansion of macro 'FOR'
   88 |  FOR(i, 0, W.size()){
      |  ^~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB n = 8
2 Correct 0 ms 256 KB n = 8
3 Correct 0 ms 384 KB n = 8
4 Correct 1 ms 256 KB n = 8
5 Correct 0 ms 256 KB n = 8
6 Correct 1 ms 256 KB n = 8
7 Correct 0 ms 256 KB n = 8
8 Correct 1 ms 256 KB n = 8
9 Correct 0 ms 256 KB n = 8
10 Correct 1 ms 256 KB n = 8
11 Correct 1 ms 256 KB n = 8
12 Correct 1 ms 384 KB n = 8
13 Correct 1 ms 416 KB n = 8
14 Correct 0 ms 256 KB n = 8
15 Correct 1 ms 256 KB n = 8

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB n = 32
2 Correct 1 ms 384 KB n = 32
3 Correct 1 ms 384 KB n = 32
4 Correct 1 ms 384 KB n = 32
5 Correct 1 ms 384 KB n = 32
6 Correct 1 ms 384 KB n = 32
7 Correct 1 ms 384 KB n = 32
8 Correct 1 ms 384 KB n = 32
9 Correct 1 ms 384 KB n = 32
10 Correct 1 ms 384 KB n = 32
11 Correct 1 ms 384 KB n = 32
12 Correct 1 ms 384 KB n = 32
13 Correct 1 ms 384 KB n = 32
14 Correct 1 ms 384 KB n = 32
15 Correct 1 ms 384 KB n = 32

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB n = 32
2 Correct 1 ms 384 KB n = 32
3 Correct 1 ms 384 KB n = 32
4 Correct 1 ms 384 KB n = 32
5 Correct 1 ms 384 KB n = 32
6 Correct 1 ms 384 KB n = 32
7 Correct 1 ms 384 KB n = 32
8 Correct 1 ms 384 KB n = 32
9 Correct 1 ms 384 KB n = 32
10 Correct 1 ms 384 KB n = 32
11 Correct 1 ms 512 KB n = 32
12 Correct 1 ms 384 KB n = 32
13 Correct 1 ms 384 KB n = 32
14 Correct 1 ms 384 KB n = 32
15 Correct 1 ms 384 KB n = 32

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB n = 128
2 Correct 2 ms 640 KB n = 128
3 Correct 2 ms 640 KB n = 128
4 Correct 2 ms 640 KB n = 128
5 Correct 2 ms 640 KB n = 128
6 Correct 2 ms 640 KB n = 128
7 Correct 2 ms 640 KB n = 128
8 Correct 2 ms 640 KB n = 128
9 Correct 2 ms 640 KB n = 128
10 Correct 3 ms 640 KB n = 128
11 Correct 3 ms 640 KB n = 128
12 Correct 2 ms 640 KB n = 128
13 Correct 2 ms 640 KB n = 128
14 Correct 2 ms 640 KB n = 128
15 Correct 2 ms 640 KB n = 128

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB n = 128
2 Correct 2 ms 640 KB n = 128
3 Correct 2 ms 640 KB n = 128
4 Correct 2 ms 640 KB n = 128
5 Correct 2 ms 544 KB n = 128
6 Correct 2 ms 640 KB n = 128
7 Correct 2 ms 640 KB n = 128
8 Correct 3 ms 640 KB n = 128
9 Correct 2 ms 640 KB n = 128
10 Correct 2 ms 640 KB n = 128
11 Correct 2 ms 640 KB n = 128
12 Correct 2 ms 640 KB n = 128
13 Correct 2 ms 640 KB n = 128
14 Correct 2 ms 640 KB n = 128
15 Correct 2 ms 640 KB n = 128