oj.uz

Submission #198160

# Submission time Handle Problem Language Result Execution time Memory
198160 2020-01-25T01:33:19 Z Benq Secret Permutation (RMI19_permutation) C++14
100 / 100
 2183 ms 504 KB 
#include "permutation.h"

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<ld,ld> pd; 
#define mp make_pair
#define f first
#define s second

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<ld> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
	return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; }
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, 
	rb_tree_tag, tree_order_statistics_node_update>; 
// change null_type for map
#define ook order_of_key
#define fbo find_by_order

void treeExample() {
	Tree<int> t, t2; t.insert(8);
	auto it = t.insert(10).f; assert(it == t.lb(9));
	assert(t.ook(10) == 1); assert(t.ook(11) == 2);
	assert(*t.fbo(0) == 8);
	t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
}

namespace input {
	template<class T> void re(complex<T>& x);
	template<class T1, class T2> void re(pair<T1,T2>& p);
	template<class T> void re(vector<T>& a);
	template<class T, size_t SZ> void re(array<T,SZ>& a);

	template<class T> void re(T& x) { cin >> x; }
	void re(double& x) { string t; re(t); x = stod(t); }
	void re(ld& x) { string t; re(t); x = stold(t); }
	template<class T, class... Ts> void re(T& t, Ts&... ts) { 
		re(t); re(ts...); 
	}

	template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
	template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
	template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
	template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}

using namespace input;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void ps() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
	}
	
	void pc() { pr("]\n"); } // debug w/ commas
	template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
	}
	#define dbg(x...) pr("[",#x,"] = ["), pc(x);
}

using namespace output;

namespace io {
	void setIn(string s) { freopen(s.c_str(),"r",stdin); }
	void setOut(string s) { freopen(s.c_str(),"w",stdout); }
	void setIO(string s = "") {
		ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
		// cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
		if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
	}
}

using namespace io;

vi ans;
vi ret;

bool use[257], done;
int N;

void dfs(int x) {
	if (x == N-1) {
		if (abs(ans[0]-ans[x]) == ret[x]) done = 1;
		return;
	}
	int nex = ans[x]-ret[x];
	//ps("??",x,ans,nex);
	if (1 <= nex && nex <= N && !use[nex]) {
		use[nex] = 1; ans.pb(nex); dfs(x+1);
		if (done) return;
		use[nex] = 0; ans.pop_back();
	}
	nex = ans[x]+ret[x];
	if (1 <= nex && nex <= N && !use[nex]) {
		use[nex] = 1; ans.pb(nex); dfs(x+1);
		if (done) return;
		use[nex] = 0; ans.pop_back();
	}
}

void solve(int _N) {
	N = _N;
	vi V; FOR(i,1,N+1) V.pb(i);
	srand(257);
	random_shuffle(all(V));
	ret.clear();
	auto ori = V;
	F0R(i,N) {
		rotate(begin(V),begin(V)+1,end(V));
		ret.pb(query(V));
	}
	int sum = 0; trav(t,ret) sum += t;
	sum /= N-1; trav(t,ret) t = sum-t;
	// answer({});
	//ps("OOPS",ret);
	FOR(i,1,N+1) {
		FOR(j,1,N+1) use[j] = 0;
		ans = {i}; use[i] = 1; done = 0; 
		dfs(0); 
		if (done) {
			//ps("HAHA",ret,ans);
			vi ANS(N);
			F0R(i,N) ANS[ori[i]-1] = ans[i];
			answer(ANS);
			return;
		}
	}
}

Compilation message

permutation.cpp: In function 'void io::setIn(std::__cxx11::string)':
permutation.cpp:142:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
permutation.cpp: In function 'void io::setOut(std::__cxx11::string)':
permutation.cpp:143:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
stub.cpp: In function 'int query(int*)':
stub.cpp:15:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(stdin, "%d", &x);
   ~~~~~~^~~~~~~~~~~~~~~~~
stub.cpp: In function 'int main(int, char**)':
stub.cpp:48:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(stdin, "%d", &N);
   ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 248 KB Output is correct
10 Correct 3 ms 248 KB Output is correct
11 Correct 3 ms 248 KB Output is correct
12 Correct 3 ms 248 KB Output is correct
13 Correct 2 ms 248 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 248 KB Output is correct
16 Correct 3 ms 376 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 248 KB Output is correct
10 Correct 3 ms 248 KB Output is correct
11 Correct 3 ms 248 KB Output is correct
12 Correct 3 ms 248 KB Output is correct
13 Correct 2 ms 248 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 248 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 21 ms 328 KB Output is correct
18 Correct 19 ms 376 KB Output is correct
19 Correct 165 ms 412 KB Output is correct
20 Correct 1552 ms 456 KB Output is correct
21 Correct 13 ms 248 KB Output is correct
22 Correct 73 ms 376 KB Output is correct
23 Correct 121 ms 376 KB Output is correct
24 Correct 2183 ms 504 KB Output is correct
25 Correct 29 ms 248 KB Output is correct
26 Correct 52 ms 376 KB Output is correct