提出 #47972996

ソースコード 拡げる

//Author : silenttkillerr
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<string>
#include<bitset>
#include<stdio.h>
#include<utility>
#include<queue>
#include<stack>
#include<deque>
#include<iterator>
#include<list>
#include<iomanip>
#include<chrono>
#include<unordered_set>
#include<string>
#include<cmath>
#include<cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0),cin.tie(0)
#define ll long long
#define cout std::cout
#define cin std::cin
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define syes cout<<"Yes"<<endl;
#define sno cout<<"No"<<endl;
#define pb push_back
#define sorta(vec) sort(vec.begin(),vec.end())
#define sortd(vec) sort(vec.begin(),vec.end(),greater<int>())
#define vll vector<vector<ll int>>
#define vl vector<ll>
#define nline "\n"
#define all(v) (v).begin(),(v).end()
#define pii pair<ll int,ll int>
#define piii pair<ll int,pair<ll int,ll int>>
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>pbds; // find_by_order, order_of_key(0-indexed)
//less , less_equal , greater , greater_equal -> rule for insertion
#define start_execution auto start = std::chrono::high_resolution_clock::now();
#define stop_execution auto stop = std::chrono::high_resolution_clock::now();
#define execution_time auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start); cerr<<"Time taken : "<<((long double)duration.count())/((long double)1e9) <<"s"<<endl; 
void entry_check(){cout<<"Entered"<<endl;}
void yn(bool res){if(res==true){yes;}else{no;}}
const ll mod=1000000007;
//const ll mod=998244353;
//ll int mod=1000000000000000000;
template<class T>
void print_v(vector<T>&vec)
{
    for(int i=0;i<vec.size();i++)
    {
        cout<<vec[i]<<" ";
    }
    cout<<endl;
}
void debug(ll int n)
{
    cout<<n<<endl;
}
void debug(int n)
{
    cout<<n<<endl;
}
void debug(string n)
{
    cout<<n<<endl;
}
void debug(vector<int>&vec)
{
    for(int i=0;i<vec.size();i++)
    {
        cout<<"[ "<<i<<" "<<vec[i]<<" ]"<<endl;
    }
}
void debug(vector<ll int>&vec)
{
    for(int i=0;i<vec.size();i++)
    {
        cout<<"[ "<<i<<" "<<vec[i]<<" ]"<<endl;
    }
}
void erase_pbds(pbds &st,ll int ele)
{
    int rank = st.order_of_key(ele);
    auto it= st.find_by_order(rank);
    st.erase(it);
}
ll int inv(ll int r)
{
	if(r==1) return 1;
	return (mod-((mod/r)*inv(mod%r))%mod+mod)%mod;
}
ll mod_add(ll int a,ll int b){a=a%mod;b=b%mod;return (((a+b)%mod)+mod)% mod;}
ll mod_mul(ll int a,ll int b){a=a%mod;b=b%mod;return (((a*b)% mod)+mod)%mod;}
ll mod_sub(ll int a, ll int b){a=a%mod;b=b%mod;return (((a - b)%mod)+mod)%mod;}
ll mod_div(ll a,ll b){a=a%mod;b=b%mod;return (a*inv(b))%mod;}
ll int ceil_div(ll int a,ll int b){return (a+b-1)/b;}
ll int gcd(ll int a,ll int b)
{
    if (!a)
    {
        return b;
    }
    return gcd(b%a,a);
}
ll int lcm(ll int a,ll int b)
{
    ll int g=__gcd(a,b);
    return (1LL*a*b)/g;
}
ll int pwr(ll int a,ll int b)
{
    if(b==0)
    {
        return 1;
    }
    if(b%2==0)
    {
        ll int ans1=pwr(a,b/2);
        ll int ans2=(ans1*ans1)%mod;
        return ans2;
    }
    ll int ans1=pwr(a,b/2);
    ll int ans2=(ans1*ans1)%mod;
    ans2=(ans2*a)%mod;
    return ans2;
}
class factorial
{
    public:
    vector<ll int>fact;
    factorial(int n)
    {
        fact.resize(n+1,0);
        fact[0]=1;
        for(int i=1;i<=n;i++)
        {
            fact[i]=mod_mul(fact[i-1],i);
        }
    }

    ll int ncr(int n,int r)
    {
        ll int a=fact[n];
        ll int b=fact[r];
        ll int c=fact[n-r];

        c=mod_mul(c,b);
        a=mod_div(a,c);
        return a;
    }
};
template<class ForwardIterator>
void read(ForwardIterator first,ForwardIterator last) 
{
    while (first != last) 
    {
        cin >> (*first);
        ++first;
    }
}
template<class T>
void read(vector<T> &v) 
{
    read(v.begin(), v.end());
}
template<class T>
void read1(vector<T>&v) 
{
    for(int i=1;i<v.size();i++)
    {
        cin>>v[i];
    }
}
ll int polynomial_hash(string & s) 
{
    const int p=31;
    const int m=1e9+9;
    //const int m=1e16+7;
    ll int hash_value = 0;
    ll int p_pow=1;
    for (char c:s) 
    {
        hash_value=(hash_value+(c-'a'+1)*p_pow)%m;
        p_pow=(p_pow*p)%m;
    }
    return hash_value;
}

bool cmp(vector<ll int>&v1,vector<ll int>&v2)
{
    if(v1[1]<v2[1])
    {
        return true;
    }
    return false;
}
//code starts here
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    //freopen("error.txt","w",stderr);
    #endif
    fast;
    start_execution
    int tt=1;
    //cin>>tt;
    for(int tc=0;tc<tt;tc++)
    {
        int n,q;
        cin>>n>>q;

        vector<int>vec(n);
        read(vec);
        map<int,int>mp;
        set<int>st;
        map<int,int>next;
        for(auto x:vec)
        {
            mp[x]++;
            st.insert(x);
            next[x]=x+1;
        }
        int mex=0;
        while(mp[mex]>0)
        {
            mex++;
        }
        while(q--)
        {
            int i,x;
            cin>>i>>x;
            i--;
            int v=vec[i];
            if(mp[v]>1)
            {
                vec[i]=x;
                mp[v]--;
                if(mex!=x)
                {
                    mp[x]++;
                }
                else
                {
                    mp[x]++;
                    int start=mex;
                    while(mp[mex]>0)
                    {
                        if(next.find(mex)==next.end())
                        {
                            next[mex]=mex+1;
                        }
                        mex=next[mex];   
                    }
                    if(mex>start)
                    {

                    next[start]=mex;
                    }
                }
            }
            else
            {
                vec[i]=x;
                if(mex<v)
                {
                    mp[v]--;
                    mp[x]++;
                    int start=mex;
                    while(mp[mex]>0)
                    {
                        if(next.find(mex)==next.end())
                        {
                            next[mex]=mex+1;
                        }
                        mex=next[mex];   
                    }
                     if(mex>start)
                    {

                    next[start]=mex;
                    }
                }
                else
                {
                    //Now at v we will have problem
                    mp[v]--;
                    mp[x]++;
                    next[v-1]=v;
                    mex=v;
                }
            }
            cout<<mex<<endl;
        }
    }
    stop_execution
    //execution_time
    return 0;
}

提出情報

提出日時
問題 E - Mex and Update
ユーザ silenttkillerr
言語 C++ 20 (gcc 12.2)
得点 0
コード長 7307 Byte
結果 WA
実行時間 1496 ms
メモリ 50928 KiB

コンパイルエラー

Main.cpp: In function ‘void debug(std::vector<int>&)’:
Main.cpp:78:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   78 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~
Main.cpp: In function ‘void debug(std::vector<long long int>&)’:
Main.cpp:85:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   85 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:47:30: warning: variable ‘start’ set but not used [-Wunused-but-set-variable]
   47 | #define start_execution auto start = std::chrono::high_resolution_clock::now();
      |                              ^~~~~
Main.cpp:215:5: note: in expansion of macro ‘start_execution’
  215 |     start_execution
      |     ^~~~~~~~~~~~~~~
Main.cpp:48:29: warning: variable ‘stop’ set but not used [-Wunused-but-set-variable]
   48 | #define stop_execution auto stop = std::chrono::high_resolution_clock::now();
      |                             ^~~~
Main.cpp:306:5: note: in expansion of macro ‘stop_execution’
  306 |     stop_execution
      |     ^~~~~~~~~~~~~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 475
結果
AC × 1
AC × 28
WA × 7
セット名 テストケース
Sample sample_01.txt
All hack_01.txt, hack_02.txt, hack_03.txt, hack_04.txt, sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt
ケース名 結果 実行時間 メモリ
hack_01.txt AC 571 ms 32036 KiB
hack_02.txt AC 617 ms 32088 KiB
hack_03.txt AC 645 ms 36684 KiB
hack_04.txt AC 667 ms 36772 KiB
sample_01.txt AC 1 ms 3448 KiB
test_01.txt AC 1 ms 3608 KiB
test_02.txt AC 1 ms 3520 KiB
test_03.txt AC 214 ms 3856 KiB
test_04.txt AC 228 ms 3844 KiB
test_05.txt AC 284 ms 4180 KiB
test_06.txt AC 643 ms 16560 KiB
test_07.txt AC 927 ms 41432 KiB
test_08.txt AC 234 ms 3848 KiB
test_09.txt AC 313 ms 4584 KiB
test_10.txt AC 754 ms 25588 KiB
test_11.txt AC 928 ms 41468 KiB
test_12.txt AC 576 ms 36696 KiB
test_13.txt WA 627 ms 32236 KiB
test_14.txt WA 781 ms 32096 KiB
test_15.txt AC 792 ms 32136 KiB
test_16.txt AC 754 ms 41392 KiB
test_17.txt AC 650 ms 41468 KiB
test_18.txt AC 839 ms 32236 KiB
test_19.txt AC 830 ms 32080 KiB
test_20.txt AC 866 ms 41384 KiB
test_21.txt AC 757 ms 41404 KiB
test_22.txt WA 1306 ms 32152 KiB
test_23.txt WA 1413 ms 32164 KiB
test_24.txt WA 1395 ms 32012 KiB
test_25.txt WA 1496 ms 32148 KiB
test_26.txt AC 225 ms 3848 KiB
test_27.txt WA 804 ms 32168 KiB
test_28.txt AC 723 ms 28720 KiB
test_29.txt AC 459 ms 22632 KiB
test_30.txt AC 886 ms 50928 KiB