結果
問題 | No.2496 LCM between Permutations |
ユーザー |
![]() |
提出日時 | 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
ソースコード
#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 longtypedef long long ll;using namespace std;//////////////////////////////////////////////////////////////////////////////////////////////////////////////これが本当の組み込み関数ってね(笑)template <typename T>T or_less(vector<T> &A, T x) { //x以下で最大要素の添字 前提: sort済み 存在しない: -1return distance(A.begin(), upper_bound(A.begin(), A.end(), x)-1);}template <typename T>T under(vector<T> &A, T x) { //x未満の最大要素の添字 前提: sort済み 存在しない: -1return 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 . //distanceのA.beginは添字を出すために常にA.begin() NG: A.begin() + 1return distance(A.begin(), lower_bound(A.begin(), A.end(), x));}template <typename T>T over(vector<T> &A, T x) { //xより大きい最小要素の添字前提: sort済み 存在しない: Nreturn distance(A.begin(), upper_bound(A.begin(), A.end(), x));}void compress(vector<ll> &A) {//小さい順に順位、大きい順にしたいならreverseはNG最後に変換 //重複無し //最初は番兵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) {//Bのbiggest 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] = pA.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] = 1A.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] = pB.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] = 1B.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);//stringでの数字の下から1桁目は 正:S.at(N-1) 誤:S.at(0)//if(S.at(i) == 1) ← charなのに1...?// modは取りましたか...?(´・ω・`)//sortの比較関数は、 a == b ならば falseを返す必要がある(そうで無いとRE)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;}