Submission #443726

#TimeUsernameProblemLanguageResultExecution timeMemory
443726valerikkSecret Permutation (RMI19_permutation)C++17
0 / 100
0 ms200 KiB
#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); 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 (stderr)

permutation.cpp: In function 'void io::setIn(std::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]
  142 |  void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
permutation.cpp: In function 'void io::setOut(std::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]
  143 |  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]
   15 |   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]
   48 |   fscanf(stdin, "%d", &N);
      |   ~~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...