結果
問題 |
No.1306 Exactly 2 Digits
|
ユーザー |
![]() |
提出日時 | 2020-12-03 12:56:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 144 ms / 2,000 ms |
コード長 | 4,221 bytes |
コンパイル時間 | 2,099 ms |
コンパイル使用メモリ | 187,120 KB |
実行使用メモリ | 25,580 KB |
平均クエリ数 | 1236.78 |
最終ジャッジ日時 | 2024-07-17 08:41:53 |
合計ジャッジ時間 | 17,149 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 123 |
ソースコード
#include <bits/stdc++.h> //#include <chrono> //#pragma GCC optimize("O2") using namespace std; #define reps(i,s,n) for(int i = s; i < n; i++) #define rep(i,n) reps(i,0,n) #define Rreps(i,n,e) for(int i = n - 1; i >= e; --i) #define Rrep(i,n) Rreps(i,n,0) #define ALL(a) a.begin(), a.end() using ll = long long; using vec = vector<ll>; using mat = vector<vec>; ll N,M,H,W,K,A,B; string S; using P = pair<ll, ll>; const ll INF = (1LL<<60); template<class T> bool chmin(T &a, const T &b){ if(a > b) {a = b; return true;} else return false; } template<class T> bool chmax(T &a, const T &b){ if(a < b) {a = b; return true;} else return false; } template<class T> void print_vector(std::vector<T> v,bool endline = true){ if(!v.empty()){ for(std::size_t i{}; i<v.size()-1; ++i) std::cout<<v[i]<<" "; std::cout<<v.back(); } if(endline) std::cout<<std::endl; } bool debug = false; vec aite; P Q(int i, int j){ if(debug){ int p = aite[i]/N - aite[j]/N, q = aite[i]%N - aite[j]%N; if(p > q) swap(p, q); return make_pair(p, q); }else { cout << "? " << i + 1 << ' ' << j + 1 << endl; int p, q; cin >> p >> q; return make_pair(p, q); } } vec calc(P p, int n, int o, bool pr = false){ vec res; rep(_, 2){ int nn = p.first, oo = p.second; nn += n; oo += o; if(pr) cout<<nn<<' '<<oo<<' '<<(nn >= 1 && nn < N && oo >= 0 && oo < N)<<endl; if(nn >= 1 && nn < N && oo >= 0 && oo < N) res.push_back(nn * N + oo); if(p.first == p.second) break; swap(p.first, p.second); } if(pr) print_vector(res); return res; } vec solve(){ map<P, vector<int> > id; reps(i, 1, N * N - N){ id[Q(i, 0)].push_back(i); } P big = id.rbegin()->first, small = id.begin()->first; if(N == 2){ if(small.first == -1) cout<<"! 3 2"<<endl; else cout<<"! 2 3"<<endl; return {}; } int n_bit, one_bit, small_id = id.begin()->second[0], big_id = id.rbegin()->second[0]; if(small.first == 0){ one_bit = 0; n_bit = 1; }else if(big.first < 0){ one_bit = n_bit = N - 1; }else if(big.first - small.first == N - 1) { one_bit = -small.first; n_bit = 1 - small.second; }else{ one_bit = -small.second; n_bit = 1 - small.first; } vec ans(N * N - N); ans[0] = n_bit * N + one_bit; for(pair<P, vector<int> > pv : id){ vec kouho = calc(pv.first, n_bit, one_bit); if(debug && kouho.empty()){ cout<<N<<endl; print_vector(aite); cout<<n_bit<<' '<<one_bit<<endl; cout<<pv.first.first<<' '<<pv.first.second<<endl; calc(pv.first, n_bit, one_bit, true); exit(0); } assert(!kouho.empty()); if(pv.second.size() == 1){ ans[pv.second[0]] = kouho[0]; }else { vec nx_kouho; if(n_bit == one_bit) nx_kouho = calc(Q(pv.second[0], small_id), 1, 0); else nx_kouho = calc(Q(pv.second[0], big_id), N - 1, N - 1); assert(!nx_kouho.empty()); rep(i, 2) { if (kouho[i] == nx_kouho[0] || (nx_kouho.size() == 2 && kouho[i] == nx_kouho[1])) ans[pv.second[0]] = kouho[i]; else ans[pv.second[1]] = kouho[i]; } } } if(debug){ return ans; }else { cout << "! "; print_vector(ans); return {}; } } int main(){ //cin.tie(nullptr); //ios::sync_with_stdio(false); cin>>N; solve(); /* random_device seed; mt19937 mt(seed()); uniform_int_distribution<> randN(3, 10), randA(0, 10000000); rep(_, 1000){ N = randN(mt); aite.resize(N * N - N); set<ll> a; reps(i, N, N * N) a.insert(i); Rreps(i, N * N - N + 1, 1){ int num = randA(mt)%i; auto ite = a.begin(); rep(j, num) ++ite; aite[N * N - N - i] = *ite; a.erase(ite); } vec res = solve(); if(aite != res){ print_vector(aite); print_vector(res); return 0; } } */ }