oj.uz

답안 #641064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641064 2022-09-15T21:49:42 Z ymm Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 2 ms 468 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#include "messy.h"

int ans[1024];

bool ask(int n, vector<int> v, int i)
{
	string s(n, '1');
	Loop (j,0,v.size())
		if (j != i)
			s[v[j]] = '0';
	return check_element(s);
}
	

void solve(int n, vector<int> vec, int bit)
{
	assert((vec.size()<<bit) == n);
	if (vec.size() == 1)
		return;
	vector<int> v[2];
	Loop (i,0,vec.size()) {
		int tmp = ask(n, vec, i);
		v[tmp].push_back(vec[i]);
		ans[vec[i]] ^= tmp << bit;
	}
	solve(n, v[0], bit+1);
	solve(n, v[1], bit+1);
}

void make(int n, int msk, int p2bit)
{
	string s;
	Loop (i,0,n) {
		if (i%p2bit != msk)
			s.push_back('1');
		else
			s.push_back('0');
	}
	Loop (i,0,n) {
		if (i%p2bit == msk && (i&p2bit)) {
			s[i] = '1';
			add_element(s);
			s[i] = '0';
		}
	}
}

std::vector<int> restore_permutation(int n, int w, int r)
{
	for (int p2bit = 1; p2bit < n; p2bit *= 2) {
		Loop (msk,0,p2bit)
			make(n, msk, p2bit);
	}
	compile_set();
	vector<int> kooft(n);
	iota(kooft.begin(), kooft.end(), 0);
	solve(n, kooft, 0);
	return vector<int>(ans, ans+n);
}

Compilation message

messy.cpp: In function 'bool ask(int, std::vector<int>, int)':
messy.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
messy.cpp:15:2: note: in expansion of macro 'Loop'
   15 |  Loop (j,0,v.size())
      |  ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from messy.cpp:1:
messy.cpp: In function 'void solve(int, std::vector<int>, int)':
messy.cpp:24:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |  assert((vec.size()<<bit) == n);
      |         ~~~~~~~~~~~~~~~~~~^~~~
messy.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
messy.cpp:28:2: note: in expansion of macro 'Loop'
   28 |  Loop (i,0,vec.size()) {
      |  ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
30.0 / 30.0

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