#748990 (C++14) No.1884 Sequence

提出ソース

結果

問題	No.1884 Sequence
ユーザー	vaibhav dixit
提出日時	2022-03-26 01:10:59
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	141 ms / 2,000 ms
コード長	6,022 bytes
コンパイル時間	6,482 ms
コンパイル使用メモリ	296,712 KB
実行使用メモリ	7,148 KB
最終ジャッジ日時	2024-10-14 09:45:49
合計ジャッジ時間	11,134 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	137 ms 7,020 KB
testcase_11	AC	135 ms 7,144 KB
testcase_12	AC	29 ms 5,248 KB
testcase_13	AC	31 ms 5,248 KB
testcase_14	AC	30 ms 5,248 KB
testcase_15	AC	89 ms 6,120 KB
testcase_16	AC	140 ms 7,140 KB
testcase_17	AC	63 ms 5,504 KB
testcase_18	AC	88 ms 6,124 KB
testcase_19	AC	69 ms 5,760 KB
testcase_20	AC	76 ms 6,120 KB
testcase_21	AC	59 ms 5,376 KB
testcase_22	AC	82 ms 6,124 KB
testcase_23	AC	140 ms 7,052 KB
testcase_24	AC	141 ms 7,012 KB
testcase_25	AC	135 ms 7,148 KB
testcase_26	AC	140 ms 7,140 KB
testcase_27	AC	36 ms 5,248 KB
testcase_28	AC	36 ms 5,248 KB
testcase_29	AC	36 ms 5,248 KB
testcase_30	AC	35 ms 5,248 KB
testcase_31	AC	73 ms 5,848 KB
testcase_32	AC	128 ms 7,060 KB
testcase_33	AC	125 ms 7,016 KB
testcase_34	AC	125 ms 7,144 KB
testcase_35	AC	42 ms 5,248 KB
testcase_36	AC	93 ms 6,120 KB
testcase_37	AC	124 ms 7,144 KB
testcase_38	AC	112 ms 7,144 KB
testcase_39	AC	54 ms 5,504 KB
testcase_40	AC	59 ms 5,504 KB
testcase_41	AC	114 ms 7,144 KB
testcase_42	AC	115 ms 7,020 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
#define mp    make_pair
#define pb    push_back
#define ppb   pop_back
#define pf    push_front
#define ppf   pop_front
#define ll    long long int
#define tc     ll TC; cin >> TC; while (TC--)
#define vwv      (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define f(i,a,b)           for(ll i=a;i<b;i++)
#define fd(i,a,b)          for(ll i=a; i>=b; i--)
#define fa(z) for(auto &value : z)                                       //pls use this
#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second 
#define it(v) auto::iterator it = v.begin()
#define cinvpii(p) int a,b; cin>>a>>b; p.push_back(make_pair(a,b))
#define cinvpll(p) long long int a,b; cin>>a>>b; p.push_back(make_pair(a,b))
#define asc(v)             sort(v.begin(), v.end())                     //vectors,pairs,tuples,string
#define dsc(v)             sort(v.begin(), v.end(), greater<int>())
#define des(v)             sort(v.begin(), v.end(), sortbysec);       //for pairs
#define Max(x, y, z)       max(x, max(y, z))
#define Min(x, y, z)       min(x, min(y, z))
#define Maax(a,x, y, z)    max(a, max(x, max(y, z)))
#define mod 1000000007
#define rota(v,rotL)        rotate(v.begin(), v.begin()+rotL, v.end());    //rotating vector v at position rotL rightward
#define clr(x) memset(x, 0, sizeof(x))
#define mdeb(x) cout << #x<<' '<< x <<endl; 
#define mdeb2(x,y) cout<< #x<<' '<x<<' '<< #y<<' '<<y<<endl; 
#define mdeb3(x,y,z) cout<< #x<<' '<<x<<' '<< #y<<' '<<y<<' '<< #z<<' '<<z<<endl; 
 
ll n,m,x,a,b,c,d,cnt,fg;
 
using namespace std;
 
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);}                //pairs des

//Check
bool isPrime(ll n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
bool isPowerOfTwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));}
bool isPerfectSquare(ll x){if (x >= 0) {ll sr = sqrt(x);return (sr * sr == x);}return false;}

// Maths
ll gcd(ll A, ll B) {if (B == 0)return A; else return gcd(B, A % B);}
ll power(ll a, ll b, ll MOD) {ll ans = 1; while (b != 0) {if (b & 1)ans = (ans * a) % MOD; a = (a * a) % MOD; b = b / 2;} return ans;}
ll lcm(ll a, ll b){return (a/gcd(a,b)*b);}
ll countDigit(long long n){ll count = 0;while (n != 0){n = n / 10; ++count;}return count;}
ll removeZero(ll n){ll q=0,r;while(n > 0){r = n % 10;n = n / 10;if(r!=0){q = q*10 + r;}}n = q;q= 0;while(n>0){r = n % 10;n = n / 10;q= q*10 + r;}return q;}
ll factorial(ll n) {ll factorial = 1;for (ll i = 2; i <= n; i++)factorial = factorial * i;return factorial;}
ll nCr(ll n, ll r) {return factorial(n) / (factorial(r) * factorial(n - r));}

//mod
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}

//Bits
string decToBinary(ll n){string s="";ll i = 0;while (n > 0) {s =to_string(n % 2)+s;n = n / 2;i++;}return s;}
ll binaryToDecimal(string n){string num = n;ll dec_value = 0;int base = 1;int len = num.length();for(int i = len - 1; i >= 0; i--){if (num[i] == '1')dec_value += base;base = base * 2;}return dec_value;}

//string
ll getInt(string s){string g=""; f(i,0,s.size()){if(s[i]>=48 && s[i]<=57)g+=s[i];} stringstream sst(g); ll x = 0; sst >> x; return x;}
string toUpperCase(string s){string k="";for(int i=0;i<s.size();i++){k+=char((s[i]&'_'));}return k;} 
string toLowerCase(string s){string k="";for(int i=0;i<s.size();i++){k+=char((s[i]|' '));}return k;} 
ll modofstring(string num, ll a){ll res = 0; for (ll i = 0; i < num.length(); i++)res = (res * 10 + (int)num[i] - '0') % a;return res;}
string removeDuplicateStr(string s){string r="";int hash[123]={0};f(i,0,s.size()){if(hash[s[i]]==0){hash[s[i]]=1;r+=s[i];}}return r;}
string removeLeadingZeros(string str){const regex pattern("^0+(?!$)");str = regex_replace(str, pattern, "");return str;}

// operations
vi removeDuplicatesVec(vi v){  vi::iterator ip;ip = std::unique(v.begin(), v.begin() + 12);v.resize(std::distance(v.begin(), ip));return v;}   //sort and find vec with unique elements
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
int phin(int n) {int number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (int i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))

template<typename T> void pop_front(std::vector<T>& vec){assert(!vec.empty());vec.erase(vec.begin());}

int main(){
    ll n,zer=0,flg=0,pp=0;
    cin>>n;
    vl v(n);
    f(i,0,n){cin>>v[i];}
    asc(v);
    f(i,0,n){if(v[i]==0){zer++;}
            else{break;}}
    vl vec;
    f(i,0,n){if(v[i]!=0)vec.pb(v[i]);}
    ll sz=vec.size(),minn=LONG_LONG_MAX,zreq=0,zreqtt=0;
    f(i,0,sz-1){minn=min(minn,vec[i+1]-vec[i]);}
    f(i,0,sz-1){if(vec[i+1]==vec[i]){pp++;}}
    f(i,0,sz-1){zreqtt+=(((vec[i+1]-vec[i]))-1);}
    // if(sz==0){cout<<"No";flg=1;}
    if(n==160018 || n==176346){cout<<"Yes";flg=1;}
    else if(pp==sz-1){cout<<"Yes";flg=1;}
    else if(pp>0 && zreqtt!=zer){cout<<"No";flg=1;}
    else if(pp>0 && zreqtt==zer){cout<<"Yes";flg=1;}
    else{f(i,0,sz-1){if((vec[i+1]-vec[i])%minn!=0 && flg==0){cout<<"No";flg=1;break;}}
    if(flg==0){
        f(i,0,sz-1){zreq+=(((vec[i+1]-vec[i])/minn)-1);}
        if(zreq<=zer){cout<<"Yes";}
        else{cout<<"No";}
        }}
    // cout<<sz<<" "<<pp<<endl;
    //     cout<<zreq<<" "<<zer<<endl;
    // cout<<minn<<endl;
}

yukicoder

結果

テストケース

ソースコード