oj.uz

답안 #203898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203898 2020-02-22T23:58:35 Z rqi Secret Permutation (RMI19_permutation) C++14
77.1429 / 100
 26 ms 376 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 #include "permutation.h"
using namespace std;
 
typedef double db;
typedef long long ll;
typedef long double ld;
typedef string str;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
 
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<cd> vcd;
 
#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)
 
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
 
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rsz resize
#define ins insert
 
const int MOD = 1e9+7; // 998244353 = (119<<23)+1
const ll INF = 1e18;
const int MX = 2e5+5;
const ld PI = 4*atan((ld)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(chrono::steady_clock::now().time_since_epoch().count());
 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
 
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define ook order_of_key
#define fbo find_by_order
 
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 = "") {
        cin.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;
 
template<class T> T invGeneral(T a, T b) {
	a %= b; if (a == 0) return b == 1 ? 0 : -1;
	T x = invGeneral(b,a); 
	return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b;
}
 
template<class T> struct modular {
	T val; 
	explicit operator T() const { return val; }
	modular() { val = 0; }
	modular(const ll& v) { 
		val = (-MOD <= v && v <= MOD) ? v : v % MOD;
		if (val < 0) val += MOD;
	}
	
	// friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; }
	friend void pr(const modular& a) { pr(a.val); }
	friend void re(modular& a) { ll x; re(x); a = modular(x); }
   
	friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; }
	friend bool operator!=(const modular& a, const modular& b) { return !(a == b); }
	friend bool operator<(const modular& a, const modular& b) { return a.val < b.val; }
 
	modular operator-() const { return modular(-val); }
	modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	modular& operator*=(const modular& m) { val = (ll)val*m.val%MOD; return *this; }
	friend modular pow(modular a, ll p) {
		modular ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend modular inv(const modular& a) { 
		auto i = invGeneral(a.val,MOD); assert(i != -1);
		return i;
	} // equivalent to return exp(b,MOD-2) if MOD is prime
	modular& operator/=(const modular& m) { return (*this) *= inv(m); }
	
	friend modular operator+(modular a, const modular& b) { return a += b; }
	friend modular operator-(modular a, const modular& b) { return a -= b; }
	friend modular operator*(modular a, const modular& b) { return a *= b; }
	
	friend modular operator/(modular a, const modular& b) { return a /= b; }
};
 
typedef modular<int> mi;
typedef pair<mi,mi> pmi;
typedef vector<mi> vmi;
typedef vector<pmi> vpmi;

int qnum[300];

int N;
int getdiff(int a, int b){
	vi q(N);
	if(a > b) swap(a, b);
	int ind = 0;
	ll sum = 0;
	for(int i = b-1; i >= a; i--){
		q[ind] = i;
		if(i != a) sum-=qnum[i-1];
		ind++;
	}
	q[ind] = b;
	ind++;
	for(int i = b+1; i <= N; i++){
		q[ind] = i;
		sum-=qnum[i-1];
		ind++;
	}
	for(int i = 1; i <= a-1; i++){
		
		q[ind] = i;
		if(i == 1){
			sum-=qnum[N];
		}
		else{
			sum-=qnum[i-1];
		}
		ind++;
	}
	return query(q)+int(sum);
}
void solve(int _N){
	N = _N;
	vi P(N, 0);
	ll sum = 0;
	for(int i = 1; i <= N; i++){
		vi q(N, 0);
		for(int j = 1; j <= N; j++){
			q[j-1] = (i+j-1)%N+1;
		}
		qnum[i] = query(q);
		sum+=ll(qnum[i]);
	}
	sum/=(N-1);
	for(int i = 1; i <= N; i++){
		qnum[i] = int(sum)-qnum[i];
		//ps(i, qnum[i]);
	}
	P[0] = 0;
	for(int i = 2; i <= N; i++){
		if(i == 2){
			P[i-1] = qnum[1];
			continue;
		}
		map<int, vi> m; //-1, 1, -1, 
		if(P[i-2]-P[i-3] == qnum[i-2]){
			m[P[i-2]-P[i-3]] = {1};
		}
		else m[P[i-2]-P[i-3]] = {-1};
		//ps("m:", i, m);
		int opt;
		for(int j = i; j <= N; j++){
			map<int, vi> m1;
			int num = qnum[j-1];
			bool flag = 0;
			for(auto u: m){
				if (!m1.count(u.f+num) && !m1.count(-u.f-num)) {
					// key no exists
					vi b = u.s;
					b.pb(1);
					m1[u.f+num] = b;
				}
				else{
					flag = 1;
					//ps("HI", i, j);
					break;
				}
				if (!m1.count(u.f-num) && !m1.count(-u.f+num)) {
					// key no exists
					vi b = u.s;
					b.pb(-1);
					m1[u.f-num] = b;
				}
				else{
					flag = 1;
					//ps("HI", i, j);
					break;
				}
			}
			if(flag == 1){
				opt = j-1;
				break;
			}
			if(j == N){
				opt = j;
				swap(m, m1);
				break;
			}
			swap(m1, m);
		}
		int num = getdiff(i-2, opt);
		
		int ind = i-1;
		//ps(i, "m:", m);
		if(!m.count(num)){
			num = -num;
		}
		//ps("getdiff(", i-2, opt, ")", num);
		//ps("BEFORE", P);
		for(auto u: m[num]){
			P[ind-1] = P[ind-2]+u*qnum[ind-1];
			ind++;
		}
		i = opt;
		//ps("AFTER", P);
		//then adds 1 to i
		continue;
	}
	//ps("Panswer: ", P);
	int mn = MOD;
	for(int i = 0; i < N; i++){
		mn = min(mn, P[i]);
	}
	for(int i = 0; i < N; i++){
		P[i] = P[i]-mn;
		P[i]++;
	}
	//ps("answer: ", P);
	answer(P);
}
 
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?), set tle
	* do smth instead of nothing and stay organized
*/

Compilation message

permutation.cpp: In function 'void io::setIn(std::__cxx11::string)':
permutation.cpp:135:35: 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:136:36: 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); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
permutation.cpp: In function 'void solve(int)':
permutation.cpp:257:7: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int opt;
       ^~~
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
11.571435 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 376 KB Partially correct
2 Partially correct 5 ms 376 KB Partially correct
3 Partially correct 5 ms 248 KB Partially correct
4 Partially correct 5 ms 376 KB Partially correct
5 Partially correct 5 ms 248 KB Partially correct
6 Partially correct 5 ms 248 KB Partially correct

Subtask #2
27.000015 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 376 KB Partially correct
2 Partially correct 5 ms 376 KB Partially correct
3 Partially correct 5 ms 248 KB Partially correct
4 Partially correct 5 ms 376 KB Partially correct
5 Partially correct 5 ms 248 KB Partially correct
6 Partially correct 5 ms 248 KB Partially correct
7 Partially correct 6 ms 376 KB Partially correct
8 Partially correct 6 ms 376 KB Partially correct
9 Partially correct 6 ms 328 KB Partially correct
10 Partially correct 6 ms 248 KB Partially correct
11 Partially correct 6 ms 248 KB Partially correct
12 Partially correct 6 ms 248 KB Partially correct
13 Partially correct 6 ms 248 KB Partially correct
14 Partially correct 6 ms 248 KB Partially correct
15 Partially correct 7 ms 248 KB Partially correct
16 Partially correct 6 ms 320 KB Partially correct

Subtask #3
38.57145 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 376 KB Partially correct
2 Partially correct 5 ms 376 KB Partially correct
3 Partially correct 5 ms 248 KB Partially correct
4 Partially correct 5 ms 376 KB Partially correct
5 Partially correct 5 ms 248 KB Partially correct
6 Partially correct 5 ms 248 KB Partially correct
7 Partially correct 6 ms 376 KB Partially correct
8 Partially correct 6 ms 376 KB Partially correct
9 Partially correct 6 ms 328 KB Partially correct
10 Partially correct 6 ms 248 KB Partially correct
11 Partially correct 6 ms 248 KB Partially correct
12 Partially correct 6 ms 248 KB Partially correct
13 Partially correct 6 ms 248 KB Partially correct
14 Partially correct 6 ms 248 KB Partially correct
15 Partially correct 7 ms 248 KB Partially correct
16 Partially correct 6 ms 320 KB Partially correct
17 Partially correct 19 ms 376 KB Partially correct
18 Partially correct 19 ms 328 KB Partially correct
19 Partially correct 16 ms 248 KB Partially correct
20 Partially correct 26 ms 332 KB Partially correct
21 Partially correct 17 ms 248 KB Partially correct
22 Partially correct 17 ms 248 KB Partially correct
23 Partially correct 17 ms 248 KB Partially correct
24 Partially correct 17 ms 248 KB Partially correct
25 Partially correct 18 ms 252 KB Partially correct
26 Partially correct 21 ms 248 KB Partially correct