#962776 (C++17) No.2684 折々の色

提出ソース

結果

問題	No.2684 折々の色
ユーザー	new_textfile
提出日時	2024-03-20 22:31:24
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	6,703 bytes
コンパイル時間	5,432 ms
コンパイル使用メモリ	272,836 KB
実行使用メモリ	68,684 KB
最終ジャッジ日時	2024-03-20 22:32:44
合計ジャッジ時間	39,553 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	2 ms 6,548 KB
testcase_03	AC	2 ms 6,548 KB
testcase_04	RE	-
testcase_05	AC	2 ms 6,548 KB
testcase_06	RE	-
testcase_07	AC	2 ms 6,548 KB
testcase_08	RE	-
testcase_09	AC	4 ms 6,548 KB
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	AC	401 ms 29,696 KB
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	AC	1,044 ms 67,120 KB
testcase_30	RE	-
testcase_31	RE	-
testcase_32	AC	1,042 ms 67,516 KB
testcase_33	AC	1,053 ms 68,248 KB
testcase_34	RE	-
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-
testcase_38	AC	1,153 ms 68,684 KB
testcase_39	AC	1,114 ms 68,684 KB
testcase_40	AC	1,146 ms 68,684 KB
testcase_41	RE	-
testcase_42	RE	-
testcase_43	AC	1,153 ms 68,684 KB
testcase_44	RE	-
testcase_45	RE	-
testcase_46	AC	1,155 ms 68,684 KB
testcase_47	RE	-
testcase_48	RE	-
testcase_49	RE	-
testcase_50	AC	2 ms 6,548 KB
testcase_51	AC	2 ms 6,548 KB
testcase_52	RE	-
testcase_53	RE	-
testcase_54	AC	2 ms 6,548 KB
testcase_55	AC	2 ms 6,548 KB
testcase_56	WA	-
testcase_57	RE	-

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
// #include <atcoder/modint>
// #include <atcoder/math>
// #include <atcoder/segtree>
// #include <atcoder/lazysegtree>
// #include <atcoder/dsu>
// #include <atcoder/scc>
using namespace atcoder;

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef priority_queue<pll, vpll, function<bool(pll,pll)> > pqpll; 
typedef priority_queue<ll, vll, function<bool(pll,pll)> > pqll;
 
struct edge{ ll to, cost; edge(ll e_to,ll e_cost): to(e_to), cost(e_cost){} };
typedef vector<vector<edge>> Graph;
 
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define LINF (1LL << 60)
#define INF (1 << 30)
#define fs first
#define sc second
#define EPS (ld)1e-10
#define ALL(a) a.begin(), a.end()
#define tcheck(a) if((clock() - start)/(ld)CLOCKS_PER_SEC >= a) break
#define debug(s) cout << #s << endl
#define debugval(x) cout << #x" = " << x << endl
 
template<typename T> ll sz(vector<T> &pos){ return (ll)pos.size(); }
template<typename T> ll sz(priority_queue<T, vector<T> > &que) {return (ll)que.size(); }
template<typename T> ll sz(priority_queue<T, vector<T>, greater<T> > &que) {return (ll)que.size(); }
ll sz(string &s) {return (ll)s.size(); } 
 
template<typename T> void chmin(T &a, T b) { if(a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if(a < b) a = b; }

// __int128_t gcd(__int128_t a, __int128_t b){ return ((!b) ? a : gcd(b,a%b)); } 
ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b; }
ll dx[4] = {0,-1,0,1},dy[4] = {-1,0,1,0};
// ll dx[8] = {0,-1,-1,-1,0,1,1,1},dy[8] = {-1,-1,0,1,1,1,0,-1};
inline bool isinside(ll i,ll n){ return (i < n && i >= 0); }

class Fraction{
    private:
    ll num,den;
    ll frac_gcd(ll _a,ll _b){ return ((!_b) ?_a :frac_gcd(_b, _a%_b)); }
    
    public:
    Fraction():num(0),den(1){}
    Fraction(ll _num, ll _den): num(_num), den(_den){
        ll sign = 1;
        if(num < 0) sign *= -1, num *= -1;
        if(den < 0) sign *= -1, den *= -1;
        ll g = frac_gcd(num,den);
        num /= g; den /= g;
        num *= sign;
    }

    bool operator!() const{return !(num);}
    bool operator==(const Fraction &f) const{
        return (this->num == f.num && this->den == f.den);
    }
    bool operator!=(const Fraction &f) const{
        return !((*this) == f);
    }

    bool operator<(const Fraction &f) const{
        if((*this) == f) return false;
        else if(this->den == 0) return false;
        else if(f.den == 0) return true;
        else return (this->num*f.den < f.num*this->den);
    }

    bool operator>(const Fraction &f) const{
        if((*this) == f) return false;
        else if(this->den == 0) return true;
        else if(f.den == 0) return false;
        else return (this->num*f.den > f.num*this->den);
    }

    bool operator<=(const Fraction &f) const{ return ((*this) == f || (*this) < f);}
    bool operator>=(const Fraction &f) const{ return ((*this) == f || (*this) > f);}

    Fraction operator+() const{ return (*this); }
    Fraction operator-() const{ return Fraction(-this->num, this->den);}

    Fraction operator+(const Fraction &f) const{ 
        assert(f.den != 0 && this->den != 0);
        return Fraction(this->num*f.den+f.num*this->den, this->den*f.den);
    }
    Fraction operator-(const Fraction &f) const{
        assert(f.den != 0 && this->den != 0);
        return Fraction(this->num*f.den-f.num*this->den, this->den*f.den);
    }
    Fraction operator*(const Fraction &f) const{
        assert(f.den != 0 && this->den != 0);
        return Fraction(this->num*f.num, this->den*f.den);
    }
    Fraction operator/(const Fraction &f) const{
        assert(f.den != 0 && this->den != 0);
        return Fraction(this->num*f.den, this->den*f.num);
    }

    Fraction operator+(const ll &x) const{ 
        assert(this->den != 0);
        return (*this)+Fraction(x,1);
    }
    Fraction operator-(const ll &x) const{
        assert(this->den != 0);
        return (*this)-Fraction(x,1);
    }
    Fraction operator*(const ll &x) const{
        assert(this->den != 0);
        return (*this)*Fraction(x,1);
    }
    Fraction operator/(const ll &x) const{
        assert(this->den != 0 && x != 0);
        return (*this)*Fraction(1,x);
    }

    Fraction& operator+=(const Fraction &f) { return (*this) = (*this) + f; }    
    Fraction& operator-=(const Fraction &f) { return (*this) = (*this) - f; }
    Fraction& operator*=(const Fraction &f) { return (*this) = (*this) * f; }
    Fraction& operator/=(const Fraction &f) { return (*this) = (*this) / f; }

    Fraction& operator+=(const ll &x) { return (*this) = (*this) + x; }    
    Fraction& operator-=(const ll &x) { return (*this) = (*this) - x; }
    Fraction& operator*=(const ll &x) { return (*this) = (*this) * x; }
    Fraction& operator/=(const ll &x) { return (*this) = (*this) / x; }

    Fraction& operator++() { return (*this) += 1; }
    Fraction& operator--() { return (*this) -= 1; }

    Fraction& operator=(ll x) { return (*this) = Fraction(x,1);}

    friend ostream &operator<<(ostream &os, const Fraction &f){
        return os << f.num << " / " << f.den;
    }
 
    friend istream &operator>>(istream &is, Fraction &f){
        ll _n,_d;
        is >> _n >> _d;
        f = Fraction(_n,_d);
        return (is);
    }

    ll floor(){ 
        assert(this->den != 0);
        return this->num / this->den;
    }

    ll ceil(){
        assert(this->den != 0);
        return (this->num+this->den-1) / this->den;
    }

    ll getdenom(){
        return this->den;
    }
    
    ll getnumer(){
        return this->num;
    }
};

int main(){
    ll n,m;
    cin >> n >> m;

    vll x(10);
    rep(i,0,m) cin >> x[i];

    vvll c(n, vll(10));
    vll t(n);
    rep(i,0,n){
        rep(j,0,m) cin >> c[i][j];
        cin >> t[i];
    }

    set<array<Fraction,10>> st;
    rep(i,0,n){
        array<Fraction,10> arr;
        rep(j,0,10) arr[j] = Fraction(10000*x[j]-100*t[i]*c[i][j], 100-t[i]);
        st.insert(arr);
    }

    rep(i,0,n){
        array<Fraction,10> arr;
        rep(j,0,10) arr[j] = Fraction(t[i]*c[i][j],1);
        if(st.count(arr) > 0){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

yukicoder

結果

テストケース

ソースコード