#1079857 (C++17) No.3126 Dual Query Problem

提出ソース

結果

問題	No.3126 Dual Query Problem
ユーザー	Leal-0
提出日時	2025-04-25 21:47:31
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	175 ms / 2,000 ms
コード長	8,742 bytes
コンパイル時間	2,857 ms
コンパイル使用メモリ	217,668 KB
実行使用メモリ	9,784 KB
最終ジャッジ日時	2025-06-20 02:43:46
合計ジャッジ時間	15,514 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

ファイルパターン	結果
sample	AC * 3
other	AC * 33

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

コンパイルメッセージ

In file included from main.cpp:4:
main.cpp: In function ‘std::string sp(std::string&)’:
main.cpp:94:26: warning: ‘besti’ may be used uninitialized [-Wmaybe-uninitialized]
   94 |     ll truerad=(rad[besti]+1)/2;
      |                          ^
main.cpp:86:9: note: ‘besti’ was declared here
   86 |     int besti;
      |         ^~~~~

ソースコード

raw source code

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__

int main() {
    int n,q; cin>>n>>q;
    vector<int> ans(n); 
    map<ll,bool> used;
    ll unused_var=1;
    ll var=0;
    rep(i,n) {
        cin>>ans[i];
        if(!used.count(ans[i])) {
            used[ans[i]]=true;
            var++;
        }
    }
    if(q<var+n) {no(); return 0;}
    ll qs=0;
    yes();
    for(pair<ll,bool> pp:used) {
        cout<<"1 "<<pp.first<<" "<<pp.first<<nl;
        qs++;
    }
    rep(i,n) {
        cout<<"2 "<<ans[i]<<nl;
        qs++;
    }
    while(qs<q) {
        cout<<"1 1 1"<<nl;
        qs++;
    }
}

/////// library zone ///////
#else
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define srep(i,l,r) for(ll i=l;i<=r;i++)
using ll = long long;
using ld = long double;
const ll mod=998244353;
#define vout(v) for(auto i :v) cout<<i<<" ";
#define INF 9223300000000000000ll
#define Winf 5e12
#define nl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vl vector<ll>

void no() { cout<<"No"<<nl;}
void yes() { cout<<"Yes"<<nl;}
void yn(bool a) {
    cout<<(a ? "Yes":"No")<<nl;
}

ll sum(vector<ll>& a) {
    ll ans=0;
    for(auto i:a) ans+=i;
    return ans;
}



string sp(string &s) { //manacher;
    string t="*#";
    rep(i,(ll)s.size()) {
        t+=s[i];
        t+="#";
    }
    t+="~";
    ll n=t.size();
    vector<ll> rad(n);
    int i=0,j=0;
    while(i<n) {
        while(i-j>=0 && i+j<n && t[i-j]==t[i+j]) ++j;
        rad[i]=j;
        int k=1;
        while(i-k>=0 && k+rad[i-k]<j) rad[i+k]=rad[i-k],++k;
        i+=k; j-=k;
    }
    rep(i,n) rad[i]--;
    
    int besti;
    rep(i,n) {
        if(i+rad[i]==n-2) {
            besti=i;break;
        }
        if(i==n-1) return "owari";
    }
    string add;
    ll truerad=(rad[besti]+1)/2;
    ll truei=(besti-rad[besti]+1-2)/2;
    add=s.substr(0,truei);
    reverse(all(add));
    return s+add;
}


vector<ll> pfact(ll n) {
    vector<ll> resp;
    vector<bool> prefact(sqrtl(n)+10);
    for(ll i=2;i*i<=n;i++) {
        while(n%i==0) {
            n/=i;
            if(!prefact[i]) resp.push_back(i);
            prefact[i]=true;
        }
    }
    if(n!=1) resp.push_back(n);
    return resp;
}

ll vecmax(vector<ll> &a) {
    ll ans=-1*INF;
    rep(i,(ll)a.size()) {
        ans=max(ans,a[i]);
    }
    return ans;
}

ll vecmin(vector<ll> &a) {
    ll ans=INF;
    rep(i,(ll)a.size()) {
        ans=min(ans,a[i]);
    }
    return ans;
}

ll safemod(ll num,ll rule) {
    return (num%rule+rule)%rule;
}

ll modinv(ll a, ll mod) { //拡張Euclidによるmodでの逆元, a*u+mod*v=1を解く
	ll b=mod,u=1,v=0;
	while (b) {
		ll t=a/b;
		a-=t*b;
        swap(a,b);
		u-=t*v;
        swap(u,v);
	}
	u%=mod; 
	if (u < 0) u+=mod;
	return u;
}


vector<ll> Erasieve(ll n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false; 

    for (int i=2;i*i<=n;++i) {
        if (is_prime[i]) {
            for (int j=i*i;j<=n;j+=i) is_prime[j] = false;
        }
    }
    vector<ll> primes;
    srep(i,2,n) {
        if (is_prime[i]) primes.push_back(i);
    }

    return primes;
}

ll divcount(ll n) {
    ll ans=0;
    for(int i=1;i*i<=n;i++) {
        if(n%i==0) ans+=(i*i==n ? 1:2);
    }
    return ans;
}

   
struct UnionFind { //Potentializedでない
    vector<int> par;  
    vector<int> rank;//これは各木のsizeに近いものを表す
    UnionFind(int N) : par(N), rank(N,0) {
        rep(i,N) {
            par[i] = i;
        }
    }
    // 経路圧縮
    int root(int x) {
        if (par[x]==x) return x;
        return par[x]=root(par[x]);
    }

    void unite(int x,int y) {
        int rx=root(x);
        int ry=root(y);
        if (rx==ry) return; 
        if (rank[rx]<rank[ry]) {
            par[rx]=ry;
        } 
        else {
            par[ry]=rx;
            if (rank[rx]==rank[ry]) {
                rank[rx]++;
            }
        }
    }

    bool same(int x,int y) {
        return root(x)==root(y);
    }
};

struct XORPotentialUF {// 0-indexed!!...これABEL群に対応は...厳しいですね...
    vector<int> par;
    vector<int> wgt;  // 各ノードの根からの XOR 差分
    vector<int> rank; // 木の高さ的な

    XORPotentialUF(int size) : par(size),wgt(size,0),rank(size,0) {
        rep(i,size) par[i]=i;
    }

    pair<int, int> find(int u) {
        if (par[u]!=u) {
            int orig_par=par[u];
            auto [root,diff]=find(orig_par);
            par[u]=root;
            wgt[u]^=diff;
            return {root,wgt[u]};
        }
        return {u,0};
    }

    bool limitunite(int u,int v,int z) {
        auto [pu,ru]=find(u);
        auto [pv,rv]=find(v);
        if (pu==pv) {
            return (ru^rv)==z;
        }
        if (rank[pu]<rank[pv]) {
            swap(pu,pv);
            swap(ru,rv);
        }

        par[pv]=pu;
        wgt[pv]=ru^rv^z;

        if (rank[pu]==rank[pv]) rank[pu]++;

        return true;
    }

    int weight(int vertex) {
        find(vertex);
        return wgt[vertex];
    }

    int diff_ytox(int x,int y) {//使う気はしない
        return weight(x)^weight(y);
    }
};



template<class ABEL> struct ADDPotentialUF { //0-indexed!! reference: https://qiita.com/drken/items/cce6fc5c579051e64fab super感謝
	vector<int> par;
	vector<int> rank;
	vector<ABEL> wgt;

	ADDPotentialUF(int size) : par(size),wgt(size,0),rank(size,0) {
        rep(i,size) par[i]=i;
    }


	pair<int, ABEL> find(int x) {
        if (par[x]==x) {
            return {x,0};
        } else {
            auto [r,w]=find(par[x]);
            par[x]=r;
            wgt[x]+=w;
            return {r,wgt[x]};
        }
    }

	ABEL weight(int x) {
		find(x);
		return wgt[x];
	}

	bool issame(int x,int y) {
		return find(x).first==find(y).first;
	}

	bool unite(int x,int y,ABEL w) {
		w+=weight(x); w-=weight(y);
		x=find(x).first; y=find(y).first;
		if (x==y) {
            return (diff_ytox(x,y)==w);
        }
		if (rank[x]<rank[y]) swap(x,y), w*=-1;
		if (rank[x]==rank[y]) ++rank[x];
		par[y]=x;
		wgt[y]=w;
		return true;
	}

	ABEL diff_ytox(int x,int y) { //同じ成分にいる前提
		return weight(y)-weight(x);
	}
};






template <class T> void vecpr(T first,T last) {
    ll tmp=0;
    for(auto it=first;it!=last;++it) {
        if(tmp) cout<<" ";
        cout<<*it;
        tmp++;
    }
    cout<<endl;
}

template <class T> void vvpr(vector<vector<T>> a) {
    for(int i=0;i<(ll)a.size();i++) {
        for(int j=0;j<(ll)a[i].size();j++) {
            if(j) cout<<" ";
            cout<<a[i][j];
        }
        cout<<endl;
    }
}

vector<ll> slmax(vector<ll> a, ll limit, ll breadth) {//slidewindowによる幅breadthでの区間最大値評価,limit=a.size()
    deque<ll> deq;
    vector<ll> max_numbers(limit, (-1)*INF);
    rep(i, limit) {
        while (!deq.empty() && deq.front() <= i - breadth) deq.pop_front();
        while (!deq.empty() && a[deq.back()] <= a[i]) deq.pop_back();
        deq.push_back(i);
        max_numbers[i] = a[deq.front()];
    }
    return max_numbers;
}

vector<ll> slmin(vector<ll> a, ll limit, ll breadth) {//slidewindowによる幅breadthでの区間最小値評価,limit=a.size()
    deque<ll> deq;
    vector<ll> min_numbers(limit, INF);
    rep(i, limit) {
        while (!deq.empty() && deq.front() <= i - breadth) deq.pop_front();
        while (!deq.empty() && a[deq.back()] >= a[i]) deq.pop_back();
        deq.push_back(i);
        min_numbers[i] = a[deq.front()];
    }
    return min_numbers;
}


ll modpow(ll fl, ll po, ll mode) {  // mode: 0=modなし, 1=modあり
    ll ret=1;
    if (mode) {
        while (po>0) {
            if (po&1) ret=(ret*fl)%mod;
            fl=(fl*fl)%mod;
            po>>=1;
        }
    } else {
        while (po>0) {
            if(po&1) ret*=fl;
            fl*=fl;
            po>>=1;
        }
    }
    return ret;
}

ll gcd(ll a,ll b) {  //Euclid
    if(a<b) return gcd(b,a);
    if(a%b==0) return b;
    return gcd(b,a%b);
}

vector<ll> lis_min(vector<ll> &a) {
    ll n=(ll)a.size();
    vector<ll> dp(n,INF);
    rep(i,n){
    auto itr = lower_bound(dp.begin(),dp.end(), a[i]);
    *itr = a[i]; 
    }
    return dp;
}//あんま使えない

vector<ll> lis_size(vector<ll>& a) { // 最長増加部分列の a index目までみたのがdp[a];
    ll n=a.size();
    vector<ll> dp(n,1);  
    vector<ll> seq;       

   rep(i,n) {
        auto it=lower_bound(seq.begin(), seq.end(), a[i]);
        
        if (it==seq.end())  seq.push_back(a[i]);
        else *it=a[i];
        dp[i]=distance(seq.begin(), lower_bound(seq.begin(), seq.end(), a[i]))+1;
    }
    srep(i,1,n-1) {
        if(dp[i]<dp[i-1]) dp[i]=dp[i-1];
    }
    return dp;
}
#endif

yukicoder

結果

コンパイルメッセージ

ソースコード