結果
問題 | No.2828 Remainder Game |
ユーザー |
|
提出日時 | 2024-08-02 22:19:48 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,267 bytes |
コンパイル時間 | 2,307 ms |
コンパイル使用メモリ | 210,180 KB |
実行使用メモリ | 25,692 KB |
平均クエリ数 | 61.30 |
最終ジャッジ日時 | 2024-08-02 22:19:54 |
合計ジャッジ時間 | 5,308 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 WA * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;void _main();int main() {_main();return 0;}using ll = long long;using ull = unsigned long long;using ld = long double;using vi = std::vector<int>;using vvi = std::vector<vi>;using vl = std::vector<ll>;using vii = std::vector<pair<int, int> >;using vvl = std::vector<vl>;using vll = std::vector<pair<ll , ll> >;using vd = std::vector<double>;using vvd = std::vector<vd>;using vs = std::vector<std::string>;using vvs = std::vector<vs>;using vb = std::vector<bool>;using vvb = std::vector<vb>;using vc = std::vector<char>;using vvc = std::vector<vc>;using pii = std::pair<int, int>;using pll = std::pair<ll, ll>;using piil = std::pair<pair<int, int>, ll>;using mii = std::map<int, int>;using mll = std::map<ll, ll>;using pql = std::priority_queue<ll>;using pqi = std::priority_queue<int>;using pqiil = std::priority_queue<pair<pair<int, int>, ll> >;using pqii = std::priority_queue<pair<int, int> >;#define pb push_back#define ps push#define eb emplace_back#define is insert#define er erase#define f first#define s second#define lb lower_bound#define ub upper_bound#define sf(i) sizeof(i)#define endl "\n"#define sz(v) ((int)(v).size())#define all(v) (v).begin(), (v).end()#define rep(i, L, R) for(ll i = L;i<=R;i++)#define pcis precisiontemplate<typename T>struct infinity {static constexpr T max=std::numeric_limits<T>::max();static constexpr T min=std::numeric_limits<T>::min();static constexpr T value=std::numeric_limits<T>::max()/2;static constexpr T mvalue=std::numeric_limits<T>::min()/2;};template<typename T>constexpr T INF=infinity<T>::value;constexpr ll lINF=INF<ll>;constexpr int iINF = INF<int>;constexpr ld PI = 3.1415926535897932384626;ll N;ll SUM = 0;// 3분이 맞나?void DNC(ll left, ll right, ll cnt, ll mod) {if (cnt == 0)return;// N+1로 나눔if (left == right) {// 확정SUM += (left)*cnt;return;}ll mid = (left+right)/2;cout << mod << " " << mid-left+1 << endl;for (ll i = left; i<=mid; i++)cout << i << " ";cout << endl;ll S;cin >> S;DNC(left, mid, S, mod);DNC(mid+1, right, cnt-S, mod);return;}using i128 = __int128_t;pair<ll,pair<ll,ll>> xGCD(ll a, ll b) {if(b == 0) return {a,{1,0}};pair<ll,pair<ll,ll>> ret = xGCD(b, a%b);ll g, x, y;g = ret.first;tie(x,y) = ret.second;return {g,{y,x-(a/b)*y}};}pair<ll,ll> CRT(vector<ll> &A, vector<ll> &M) {if(A.size() != M.size()) return {-1,-1};int N = A.size();ll a1 = A[0];ll m1 = M[0];for(int i=1; i<N; ++i) {ll a2 = A[i];ll m2 = M[i];a2 %= m2;ll g = __gcd(m1, m2);if(a1 % g != a2 % g) return {-1,-1};ll p, q;auto res = xGCD(m1/g, m2/g);tie(p,q) = res.second;i128 mod = (i128)m1 / g * m2;a1 = ((i128)a1 * (m2/g) % mod) * q % mod + ((i128)a2*(m1/g)%mod)*p % mod;a1 = (a1 + mod) % mod;m1 = mod;}return {a1, m1};}// 알아서 양수 해를 구해줌void _main() {// N으로 나눈 나머지 이분cin >> N;vl lst;DNC(0, 30, 5, 31);lst.pb(SUM);SUM = 0;DNC(0, 36, 5, 37);lst.pb(SUM);SUM = 0;DNC(0, 4, 5, 5);lst.pb(SUM);SUM = 0;vl M;M.pb(31);M.pb(37);M.pb(5);auto [a,b] = CRT(lst, M);cout << 0<< " " << 1 << endl;cout <<a << endl;}