結果
問題 | No.2732 Similar Permutations |
ユーザー |
|
提出日時 | 2024-04-19 23:14:02 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,802 ms / 2,000 ms |
コード長 | 2,634 bytes |
コンパイル時間 | 5,590 ms |
コンパイル使用メモリ | 312,932 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2024-10-11 17:37:16 |
合計ジャッジ時間 | 25,497 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 101 |
ソースコード
#include <bits/stdc++.h>using namespace std;//*/#include <atcoder/all>using namespace atcoder;#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")#pragma GCC target("avx,avx2,fma")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")//*/#define rep(i,n) for(int i=0;i<n;i++)#define Rep(i,a,b) for(int i=a;i<b;i++)#define ALL(x) (x).begin(),(x).end()#define dbgv(x); for(auto now : x) cout << now << " "; cout << endl;//using P = pair<int,int>;using ll = long long;using ull = unsigned long long;//*/template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef vector<ll> vll;typedef vector<int> vint;random_device rnd;mt19937 rng(rnd());using mint = modint998244353;class Timer {public:Timer() {begin();elapsed_time_ = 0.0;}void begin() {start_time_ = chrono::system_clock::now();}double get_time() {chrono::system_clock::time_point end_time = chrono::system_clock::now();elapsed_time_ = chrono::duration_cast<std::chrono::nanoseconds>(end_time - start_time_).count();elapsed_time_ *= 1e-9; // nanoseconds -> secondsreturn elapsed_time_;}double get_last_time() const {return elapsed_time_;}bool yet(double time_limit) {return get_time() < time_limit;}double progress(double time_limit) {return get_time() / time_limit;}private:chrono::system_clock::time_point start_time_;double elapsed_time_;};constexpr double time_limit = 1.8;void solve(){Timer timer;int n; cin >> n;if(n==1){cout << -1 <<endl;return;}vint a(n); rep(i,n) cin >> a[i];vint p(n),q(n); rep(i,n) p[i] = i+1,q[i] = i+1;while(timer.yet(time_limit)){int i = rng()%n;int j = rng()%n;while(i==j) j = rng()%n;if(rng()%1000 <= 300){swap(p[i],p[j]);swap(q[i],q[j]);}if(((a[i]+p[i])^(a[j]+p[j])) == ((a[i]+p[j])^(a[j]+p[i]))){//cout << ((a[i]+p[i])^(a[j]+p[j])) << " " << ((a[i]+p[i])^(a[j]+p[j])) << endl;swap(q[i],q[j]);dbgv(p);dbgv(q);return;}}cout << -1 << endl;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1; //cin >> t;rep(dirc,t) solve();}