結果

問題 No.2496 LCM between Permutations
ユーザー Astral__
提出日時 2023-10-06 22:20:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 88 ms / 2,000 ms
コード長 9,788 bytes
コンパイル時間 2,244 ms
コンパイル使用メモリ 216,792 KB
最終ジャッジ日時 2025-02-17 05:15:45
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /usr/include/c++/13/istream:41,
                 from /usr/include/c++/13/sstream:40,
                 from /usr/include/c++/13/complex:45,
                 from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127,
                 from main.cpp:1:
In member function ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>]’,
    inlined from ‘solve()::<lambda(ll, ll)>’ at main.cpp:177:33,
    inlined from ‘void solve()’ at main.cpp:330:23:
/usr/include/c++/13/ostream:204:25: warning: ‘tmp’ may be used uninitialized [-Wmaybe-uninitialized]
  204 |       { return _M_insert(__n); }
      |                ~~~~~~~~~^~~~~
main.cpp: In function ‘void solve()’:
main.cpp:315:8: note: ‘tmp’ was declared here
  315 |     ll tmp;
      |        ^~~
main.cpp:346:9: warning: ‘pre’ may be used uninitialized [-Wmaybe-uninitialized]
  346 |     B.at(pre) = p;
      |     ~~~~^~~~~
main.cpp:316:8: note: ‘pre’ was declared here
  316 |     ll pre;
      |        ^~~
In member function ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>]’,
    inlined from ‘solve()::<lambda(ll, ll)>’ at main.cpp:177:21,
    inlined from ‘void solve()’ at main.cpp:265:23:
/usr/include/c++/13/ostream:204:25: warning: ‘tmp’ may be used uninitialized [-Wmaybe-uninitialized]
  204 |       { return _M_insert(__n); }
      |                ~~~~~~~~~^~~~~
main.cpp: In function ‘void solve()’:
main.cpp:246:6: note: ‘tmp’ was declared here
  246 |   ll tmp;
      |      ^~~
main.cpp:282:9: warning: ‘pre’ may be used uninitialized [-Wmaybe-uninitialized]
  282 |     A.at(pre) = p;
      |     ~~~~^~~~~
main.cpp:247:6: note: ‘pre’ was declared

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define PPque priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>>
#define Pque priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
#define pque priority_queue<ll, vector<ll>, greater<ll>>
#define umap unordered_map
#define uset unordered_set
#define rep(i, s, f) for(ll i = s; i <= f; i++)
#define per(i, s, f) for(ll i = s; i >= f; i--)
#define all0(x) (x).begin() ,(x).end()
#define all(x) (x).begin() + 1, (x).end()
#define vvvvl vector<vvvl>
#define vvvi vector<vector<vector<int>>>
#define vvvl vector<vector<vector<ll>>>
#define vvvc vector<vector<vector<char>>>
#define vvvd vector<vector<vector<double>>>
#define vvvm vector<vector<vector<mint>>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvs vector<vector<string>>
#define vvc vector<vector<char>>
#define vvp vector<vector<pair<ll, ll>>>
#define vvb vector<vector<bool>>
#define vvd vector<vector<double>>
#define vvm vector<vector<mint>>
#define vp vector<pair<ll, ll>>
#define vi vector<int>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vd vector<double>
#define vm vector<mint>
#define P pair<ll, ll>
#define TU tuple<ll, ll, ll>
#define rrr(l, r) mt()%(r-l+1)+l
#define ENDL '\n'
#define ull unsigned long long
typedef long long ll;
using namespace std;
////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
template <typename T>
T or_less(vector<T> &A, T x) { //x : sort : -1
return distance(A.begin(), upper_bound(A.begin(), A.end(), x)-1);
}
template <typename T>
T under(vector<T> &A, T x) { //x : sort : -1
return distance(A.begin(), lower_bound(A.begin(), A.end(), x)-1);
}
template <typename T>
T or_more(vector<T> &A, T x) { //x  : sort : N . //distanceA.beginA.begin() NG: A
    .begin() + 1
return distance(A.begin(), lower_bound(A.begin(), A.end(), x));
}
template <typename T>
T over(vector<T> &A, T x) { //x: sort : N
return distance(A.begin(), upper_bound(A.begin(), A.end(), x));
}
void compress(vector<ll> &A) {//reverseNG // //
vector<ll> temp = A;
sort(temp.begin()+1, temp.end());
temp.erase(unique(temp.begin()+1, temp.end()), temp.end());
for (int i = 1; i <= int(A.size()-1); i++) {
A.at(i) = distance(temp.begin(), lower_bound(temp.begin()+1, temp.end(), A.at(i)));
}
}
template <typename T>
void UNIQUE(vector<T> &A) {
sort(all0(A));
return A.erase(unique(A.begin(), A.end()), A.end());
}
template <typename T>
void rev90(vector<vector<T>> &A, int indexed = 1) {
reverse(A.begin() + indexed, A.end());
int n = A.size();
rep(i, indexed, n-1) {
rep(j, i+1, n-1) {
swap(A.at(i).at(j), A.at(j).at(i));
}
}
}
void chmin(ll &a, ll b) {
a = min(a, b);
}
void chmax(ll &a, ll b) {
a = max(a, b);
}
//////////////////////////////////////////////////////////////////////
//
///////////////////////////////////////////////////////////////////////
ll round(ll x, ll i) {return ll(x + 5 * pow(10, i-1))/ll(pow(10, i)) * ll(pow(10, i));}
vp insu_bunkai(ll N) {
vp res;
for (int i = 2; i * i <= N; i++) {
ll cnt = 0;
while(N % i == 0) {
cnt++;
N /= i;
}
if(cnt != 0) res.push_back(P(i, cnt));
}
if(N != 1) res.push_back(P(N, 1));
return res;
}
ll extgcd (ll a, ll b, ll &x, ll &y) {
if(b == 0) { x = 1;y = 0;return a;}
ll d = extgcd(b, a%b, y, x);
y -= a/b * x;
return d;
}
template <typename T>
T ceil(T a, T b) {
assert(b != 0);
if(a % b == 0) return a / b;
if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1;
else return a / b;
}
template <typename T>
T floor(T a, T b) {
assert(b != 0);
if(a % b == 0) return a / b;
if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b;
else return a/b - 1;
}
ll modpow(ll x, ll y) {
const ll mod = 9223372036854775807LL;
if(x > mod) x %= mod;
if(y == 0) return 1;
ll res = modpow(x, y >> 1);
res = res * res % mod;
if(y & 1) res *= x, res %= mod;
return res;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
const ll int_max = 1001001001;
const ll ll_max = 1001001001001001001LL;
const double pi = 3.141592653589793;
vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1}; // () → ↓ ← ↑ ※  
vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1};
//const ll mod = 1000000007;
//const ll mod = 998244353;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
vector<ll> Exhurui(ll N) {
vector<ll> sosu;
ll Max = sqrt(N);
vector<int> hantei(N+1, 1);
hantei.at(1) = 0;
for (int i = 2; i <= Max; i++) {
if (hantei.at(i) == 1) {
for (int j = 2; j * i <= N; j++) {
hantei.at(j*i) = 0;
}
}
}
for (int i = 2; i <= N; i++) {
if (hantei.at(i) == 1) {
sosu.push_back(i);
}
}
return sosu;
}
void solve() {
ll N;
cin >> N;
auto a = [](ll a, ll b) {
cout << "? " << a << " " << b << endl;
ll res;
cin >> res;
return res;
};
if(N == 1) {
cout << "! " << 1 << " " << 1;
exit(0);
}
else if(N==2) {
ll r1 = a(1, 1);
ll r2 = a(1, 2);
vl A(3);
vl B(3);
if(r1 == 2 && r2 == 2) {
A.at(1) = 2;
A.at(2) = 1;
rep(i, 1, 2) {
B.at(i) = a(2, i);
}
}
else {
A.at(1) = 1;
A.at(2) = 2;
rep(i, 1, 2) {
B.at(i) = a(1, i);
}
}
cout <<"! " << A[1] << " " << A[2] << " " << B[1] << " " << B[2];
exit(0);
}
auto primes = Exhurui(N);
ll p = primes.back();//
ll idx = 1;
bool aaa = false;
for( ; idx <= N; idx++) {
cout <<"? " << 1 << " " << idx << endl;
ll res;
cin >> res;
if(res % p == 0) {
if(idx == 1) {
ll res2 = a(1, 2);
if(res2 % p == 0) {
aaa = true;
}
else {
break;
}
}
else {
break;
}
}
}
//if(aaa) A[1] p
//else B[idx] p  N
if(!aaa) {
//Bbiggest prime idx
vl A(N+1, -1);
vl B(N+1, -1);
B[idx] = p;
ll tmp;
ll pre;
rep(i, 1, N) {
cout << "? " << i << " " << idx << endl;
ll res;
cin >> res;
A.at(i) = res / p;
if(A.at(i) == 1) {
pre = tmp;
tmp = i;
}
}
//2N
//A[tmp]1 or p
vp rres;
rep(i, 1, 3) {
if(i == idx) continue;
rres.push_back(P(a(tmp, i), i));
if(rres.size() >= 2) break;
}
//2N + 2
if(rres.at(0).first % p == 0 && rres.at(1).first % p == 0) {
//A[tmp] = p
A.at(tmp) = p;
tmp = pre;
auto [r1, i1] = rres.at(0);
B.at(i1) = r1 / p;
auto [r2, i2] = rres.at(1);
B.at(i2) = r2 / p;
}
else {
//A[tmp] = 1
A.at(pre) = p;
auto [r1, i1] = rres.at(0);
B.at(i1) = r1;
auto [r2, i2] = rres.at(1);
B.at(i2) = r2;
}
rep(i, 1, N) {
if(B.at(i) != -1) continue;
cout << "? " << tmp << " " << i << endl;
ll res;
cin >> res;
//(1, B.at(i)) (p, B.at(i))
B.at(i) = res;
}
cout <<"! ";
rep(i, 1, N) cout << A.at(i) << " ";
rep(i, 1, N) cout << B.at(i) << " ";
}
else {
vl A(N+1, -1);
vl B(N+1, -1);
A.at(1) = p;
//N
ll tmp;
ll pre;
rep(i, 1, N) {
B.at(i) = a(1, i) / p;
if(B.at(i) == 1) {
pre = tmp;
tmp = i;
}
}
//2N
//B[tmp]1 or p
vp rres;
rep(i, 2, 3) {
rres.push_back(P(a(i, tmp), i));
}
//2N + 2
if(rres.at(0).first % p == 0 && rres.at(1).first % p == 0) {
//B[tmp] = p
B.at(tmp) = p;
tmp = pre;
auto [r1, i1] = rres.at(0);
A.at(i1) = r1 / p;
auto [r2, i2] = rres.at(1);
A.at(i2) = r2 / p;
}
else {
//B[tmp] = 1
B.at(pre) = p;
auto [r1, i1] = rres.at(0);
A.at(i1) = r1;
auto [r2, i2] = rres.at(1);
A.at(i2) = r2;
}
rep(i, 1, N) {
if(A.at(i) != -1) continue;
cout << "? " << i << " " << tmp << endl;
ll res;
cin >> res;
//(1, B.at(i)) (p, B.at(i))
A.at(i) = res;
}
cout <<"! ";
rep(i, 1, N) cout << A.at(i) << " ";
rep(i, 1, N) cout << B.at(i) << " ";
}
}
//2( :(x / 2) :floor<ll>(x, 2);
//string1 :S.at(N-1) :S.at(0)
//if(S.at(i) == 1) ← char1...?
// mod...?(´ω)
//sort a == b  falseRE
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(15);
ll T = 1;
//cin >> T;
rep(i, 1, T) {
solve();
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0