#707603 (C++14) No.1711 Divide LCM

提出ソース

結果

問題	No.1711 Divide LCM
ユーザー	mtsd
提出日時	2021-10-15 23:12:50
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	12,083 bytes
コンパイル時間	2,374 ms
コンパイル使用メモリ	197,728 KB
実行使用メモリ	59,136 KB
最終ジャッジ日時	2023-10-17 21:00:42
合計ジャッジ時間	18,879 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	3 ms 4,348 KB
testcase_04	AC	12 ms 4,348 KB
testcase_05	AC	67 ms 4,860 KB
testcase_06	AC	18 ms 4,348 KB
testcase_07	AC	50 ms 4,708 KB
testcase_08	AC	19 ms 4,356 KB
testcase_09	AC	134 ms 5,764 KB
testcase_10	AC	25 ms 4,348 KB
testcase_11	AC	216 ms 6,584 KB
testcase_12	AC	26 ms 4,348 KB
testcase_13	AC	3 ms 4,348 KB
testcase_14	AC	8 ms 4,348 KB
testcase_15	AC	12 ms 4,348 KB
testcase_16	AC	3 ms 4,348 KB
testcase_17	AC	8 ms 4,348 KB
testcase_18	AC	129 ms 8,720 KB
testcase_19	AC	129 ms 8,712 KB
testcase_20	AC	130 ms 8,720 KB
testcase_21	AC	149 ms 10,752 KB
testcase_22	TLE	-
testcase_23	AC	94 ms 6,396 KB
testcase_24	AC	364 ms 15,508 KB
testcase_25	AC	370 ms 15,508 KB
testcase_26	AC	351 ms 15,504 KB
testcase_27	AC	346 ms 15,868 KB
testcase_28	AC	336 ms 15,320 KB
testcase_29	AC	5 ms 4,348 KB
testcase_30	AC	441 ms 19,916 KB
testcase_31	AC	5 ms 4,348 KB
testcase_32	AC	339 ms 23,672 KB
testcase_33	AC	310 ms 23,672 KB
testcase_34	AC	17 ms 4,348 KB
testcase_35	AC	484 ms 15,284 KB
testcase_36	AC	540 ms 16,112 KB
testcase_37	AC	533 ms 16,112 KB
testcase_38	AC	159 ms 15,036 KB
testcase_39	AC	368 ms 26,188 KB
testcase_40	AC	4 ms 4,348 KB
testcase_41	AC	4 ms 4,348 KB
testcase_42	AC	4 ms 4,348 KB
testcase_43	AC	4 ms 4,348 KB
testcase_44	AC	5 ms 4,348 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:206:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  206 |     for(auto [x,c]:mx){
      |              ^
main.cpp: In lambda function:
main.cpp:230:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  230 |                 for(auto [p,e]:a[i]){
      |                          ^
main.cpp: In function 'int main()':
main.cpp:271:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  271 |         for(auto [p,e]:a[i]){
      |                  ^

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define inf 1000000007
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define rrep(i,n) for(int i = (int)n-1; i >= 0; --i)
#define srep(i,a,b) for(int i = (int)a; i < (int)(b); ++i)
#define all(x) (x).begin(),(x).end()
#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define SZ(c) (int)(c).size()
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
    os << "{";
    for (int i = 0; i<(int)vec.size(); i++) {
        os << vec[i] << (i + 1 == (int)vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// pair出力
template<typename T, typename U>
ostream& operator << (ostream& os, pair<T, U> pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// map出力
template<typename T, typename U>
ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "{";
    for(auto itr = map_var.begin(); itr != map_var.end(); itr++){
        os << "(" << itr->first << ", " << itr->second << ")";
        itr++;
        if(itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set 出力
template<typename T>
ostream& operator << (ostream& os, set<T>& set_var) {
    os << "{";
    for(auto itr = set_var.begin(); itr != set_var.end(); itr++){
        os << (*itr);
        ++itr;
        if(itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
#define overload2(_1, _2, name, ...) name
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size)                                                                                                                                  \
    vector<type> name(size);                                                                                                                                   \
    IN(name)
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w)                                                                                                                                   \
    vector<vector<type>> name(h, vector<type>(w));                                                                                                             \
    IN(name)
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)                                                                                                                         \
    vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define INT(...)                                                                                                                                               \
    int __VA_ARGS__;                                                                                                                                           \
    IN(__VA_ARGS__)
#define LL(...)                                                                                                                                                \
    ll __VA_ARGS__;                                                                                                                                            \
    IN(__VA_ARGS__)
#define STR(...)                                                                                                                                               \
    string __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
#define CHR(...)                                                                                                                                               \
    char __VA_ARGS__;                                                                                                                                          \
    IN(__VA_ARGS__)
#define DBL(...)                                                                                                                                               \
    double __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
int scan() { return getchar(); }
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
template <class T> void scan(vector<T> &);
template <class T> void scan(vector<T> &a) {
    for(auto &i : a) scan(i);
}
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
    scan(head);
    IN(tail...);
}
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define dbg(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define dbg(...) (void(0))
#define dump(x) (void(0))
#endif
template<typename A, typename T>
std::enable_if_t<std::is_convertible<T, A>::value> fill(A& array, const T& val)
{
    array = val;
}
template<typename A, typename T>
std::enable_if_t<!std::is_convertible<T, A>::value> fill(A& array, const T& val)
{
    for (auto& a : array) {
        fill(a, val);
    }
}
template <class T> T ceil(T x, T y) {assert(y >= 1);return (x > 0 ? (x + y - 1) / y : x / y);}
template <class T> T floor(T x, T y) {assert(y >= 1);return (x > 0 ? x / y : (x + y - 1) / y);}
vector<int> iota(int n) {vector<int> a(n);iota(all(a), 0);return a;}
template <class T> T POW(T x, int n) {T res = 1;for(; n; n >>= 1, x *= x){if(n & 1) res *= x;}return res;}
ll pow2(int i) { return 1LL << i; }
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int lowbit(ll a) { return a == 0 ? 64 : __builtin_ctzll(a); }
// int allbit(int n) { return (1 << n) - 1; }
ll allbit(ll n) { return (1LL << n) - 1; }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }


template <class S> void fold_in(vector<S> &v) {}
template <typename Head, typename... Tail, class S> void fold_in(vector<S> &v, Head &&a, Tail &&...tail) {
    for(auto e : a) v.emplace_back(e);
    fold_in(v, tail...);
}
template <class S> void renumber(vector<S> &v) {}
template <typename Head, typename... Tail, class S> void renumber(vector<S> &v, Head &&a, Tail &&...tail) {
    for(auto &&e : a) e = lb(v, e);
    renumber(v, tail...);
}
template <class S, class... Args> void zip(vector<S> &head, Args &&...args) {
    vector<S> v;
    fold_in(v, head, args...);
    sort(all(v)), v.erase(unique(all(v)), v.end());
    renumber(v, head, args...);
}
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}

int main(){
    INT(n);
    vector<vector<pair<int,int> > > a;
    vector<int> num(n,1);
    map<int,int> mx;
    rep(i,n){
        INT(m);
        vector<pair<int,int> > q;
        rep(j,m){
            INT(p,e);
            chmax(mx[p],e);
            q.push_back({p,e});
            rep(zz,e)num[i] *= p;
        }
        a.push_back(q);
    }
    vector<int> pr;
    for(auto [x,c]:mx){
        pr.push_back(x);
    }
    reverse(all(pr));
    ll K = 1;
    ll cc = 0;
    vector<int> ans;
    for(auto x:pr){
        cc++;
        K *=x;
        ans.push_back(x);
        if(K>=1000000000){
            break;
        }
    }
    auto answer = [&]()->vector<vector<int> >{
        vector<vector<int> > r;
        vector<char> flag(n);
        dbg(ans);
        rep(z,ans.size()){
            vector<int> ttt;
            rep(i,n){
                bool fff = 1;
                if(flag[i])continue;
                for(auto [p,e]:a[i]){
                    if(ans[z]==p){
                        if(mx[p]==e)fff = 0;
                    }
                }
                if(fff){
                    ttt.push_back(i);
                    flag[i] = 1;
                }
            }
            r.push_back(ttt);
        }
        rep(i,n){
            if(!flag[i]){
                return vector<vector<int>>();
            }
        }
        return r;
    };
    if(cc==2){
        vector<vector<int> > res = answer();
        if(res.size()==0){
            cout << -1 << endl;
            return 0;
        }
        cout << res.size() << "\n";
        for(auto&v:res){
            cout << v.size() << " ";
            for(auto x:v){
                cout << num[x] << " ";
            }
            cout << "\n";
        }
        return 0;
    }

    map<int,int> mp;
    map<int,int> cnt;
    vector<vector<int> > s(n);
    rep(i,n){
        vector<int> t;
        for(auto [p,e]:a[i]){
            if(mx[p]==e){
                t.push_back(p);
            }
        }
        if(t.size()==mx.size()){
            cout << -1 << endl;
            return 0;
        }
        s[i] = t;
        int N = t.size();
        vector<int>pp(1<<N);
        pp[0] = 1;
        rep(bits,1<<N){
            if(bits==0)continue;
            int bb = topbit(bits);
            pp[bits] = pp[bits^(1<<bb)] * t[bb];
            mp[pp[bits]]++;
            cnt[pp[bits]] = popcount(bits);
        }
    }
    dbg(num);
    dbg(mp);
    srep(c,2,cc){
        bool ok = 0;
        vector<int> tmp;
        auto dfs = [&](auto&&f,int X,int s,int id)->void{
            if(s==c){
                if(mp[X]==0){
                    ok = 1;
                    ans = tmp;
                }
                return;
            }
            if(id==pr.size())return;
            int p = pr[id];
            tmp.push_back(p);
            f(f,X*p,s+1,id+1);
            if(ok)return;
            tmp.pop_back();
            f(f,X,s,id+1);
        };
        dfs(dfs,1,0,0);
        if(ok){
            vector<vector<int> > res = answer();
            if(res.size()==0){
                cerr<< "error" << endl;
                cout << -1 << endl;
                return 0;
            }
            cout << res.size() << "\n";
            for(auto&v:res){
                cout << v.size() << " ";
                for(auto x:v){
                    cout << num[x] << " ";
                }
                cout << "\n";
            }
            return 0;
        }
    }
    vector<vector<int> > res = answer();
    if(res.size()==0){
        cout << -1 << endl;
        return 0;
    }
    cout << res.size() << "\n";
    for(auto&v:res){
        cout << v.size() << " ";
        for(auto x:v){
            cout << num[x] << " ";
        }
        cout << "\n";
    }
    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード