結果

問題 No.2496 LCM between Permutations
ユーザー kotatsugame
提出日時 2023-10-06 22:23:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,907 bytes
コンパイル時間 1,399 ms
コンパイル使用メモリ 98,008 KB
実行使用メモリ 25,476 KB
平均クエリ数 926.72
最終ジャッジ日時 2024-07-26 16:35:05
合計ジャッジ時間 4,385 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26 WA * 1 QLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:105:24: warning: 'T' may be used uninitialized [-Wmaybe-uninitialized]
  105 |         A[askid]=T[mini];
      |                  ~~~~~~^
main.cpp:97:13: note: 'T' declared here
   97 |         int T[1000];
      |             ^
main.cpp:94:21: warning: 'a' may be used uninitialized [-Wmaybe-uninitialized]
   94 |                 A[a]=B[b]=1;
      |                 ~~~~^~~~~~~
main.cpp:84:21: note: 'a' was declared here
   84 |                 int a,b;
      |                     ^
main.cpp:94:26: warning: 'b' may be used uninitialized [-Wmaybe-uninitialized]
   94 |                 A[a]=B[b]=1;
      |                      ~~~~^~
main.cpp:84:23: note: 'b' was declared here
   84 |                 int a,b;
      |                       ^

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<cstdlib>
using namespace std;
const bool debug=false;
int gcd(int a,int b)
{
    while(b)
    {
        int t=a%b;
        a=b;
        b=t;
    }
    return a;
}
bool isp[1001];
int N;
int A[1000],B[1000];
int aA[1000],aB[1000];
int ask(int i,int j)
{
    cout<<"? "<<i+1<<" "<<j+1<<endl;
    if(debug)return aA[i]*aB[j]/gcd(aA[i],aB[j]);
    int x;cin>>x;
    return x;
}
void answer()
{
    cout<<"!";
    for(int i=0;i<N;i++)cout<<" "<<A[i];
    for(int i=0;i<N;i++)cout<<" "<<B[i];
    cout<<endl;
    if(debug)
    {
        for(int i=0;i<N;i++)if(aA[i]!=A[i]||aB[i]!=B[i])
        {
            cout<<"WA"<<endl;
            exit(1);
        }
        cout<<"AC"<<endl;
    }
    exit(0);
}
#include<random>
mt19937 rng;
void setup()
{
    random_device seed_gen;
    unsigned int seed=seed_gen();
    //seed=1604191338;
    if(debug)cout<<"seed = "<<seed<<endl;
    rng=mt19937(seed);
    if(!debug)return;
    N=rng()%100+1;
    for(int i=0;i<N;i++)aA[i]=aB[i]=i+1;
    shuffle(aA,aA+N,rng);
    shuffle(aB,aB+N,rng);
    cout<<"answer =";
    for(int i=0;i<N;i++)cout<<" "<<aA[i];
    for(int i=0;i<N;i++)cout<<" "<<aB[i];
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    setup();
    if(!debug)cin>>N;
    for(int i=2;i<=N;i++)isp[i]=true;
    for(int i=2;i<=N;i++)if(isp[i])
    {
        for(int j=i+i;j<=N;j+=i)isp[j]=false;
    }
    if(N==1)
    {
        A[0]=B[0]=1;
        answer();
    }
    if(N==2)
    {
        bool fn=false;
        int a,b;
        for(int i=0;!fn&&i<2;i++)for(int j=0;!fn&&j<2;j++)
        {
            if(ask(i,j)==1)
            {
                a=i,b=j;
                fn=true;
            }
        }
        A[0]=A[1]=B[0]=B[1]=2;
        A[a]=B[b]=1;
        answer();
    }
    int T[1000];
    int mini=0;
    int askid=rng()%N;
    for(int i=0;i<N;i++)
    {
        T[i]=ask(askid,i);
        if(T[mini]>T[i])mini=i;
    }
    A[askid]=T[mini];
    int cnt[1001]={};
    for(int i=0;i<N;i++)
    {
        assert(T[i]%A[askid]==0);
        cnt[T[i]/A[askid]]++;
    }
    vector<pair<int,int> >Ps;
    for(int i=0;i<N;i++)
    {
        if(cnt[T[i]/A[askid]]>1)continue;
        int p=T[i]/A[askid];
        if(!isp[p]||p*3<=N)continue;
        Ps.push_back(make_pair(p,i));
        B[i]=p;
    }
    assert(!Ps.empty());
    sort(Ps.begin(),Ps.end());
    int P=Ps.back().first,Pi=Ps.back().second;
    for(int i=0;i<N;i++)if(i!=askid)
    {
        int v=ask(i,Pi);
        assert(v%P==0);
        A[i]=v/P;
    }
    vector<int>one;
    for(int i=0;i<N;i++)if(A[i]==1)one.push_back(i);
    assert(one.size()==2);
    int ONE;
    if(Ps.size()>=2)
    {
        if(ask(one[0],Ps[0].second)%P!=0)ONE=one[0];
        else ONE=one[1];
    }
    else
    {
        vector<int>test;
        for(int i=0;i<N;i++)if(i!=Pi)test.push_back(i);
        assert(test.size()>=2);
        shuffle(test.begin(),test.end(),rng);
        shuffle(one.begin(),one.end(),rng);
        if(ask(one[0],test[0])%P!=0||ask(one[0],test[1])%P!=0)ONE=one[0];
        else ONE=one[1];
    }
    A[one[0]+one[1]-ONE]=P;
    for(int i=0;i<N;i++)if(B[i]==0)B[i]=ask(ONE,i);
    if(P*2<=N)
    {
        vector<int>two;
        for(int i=0;i<N;i++)if(A[i]==2)two.push_back(i);
        assert(two.size()==2);
        int O=0;
        while(B[O]!=1)O++;
        if(ask(two[0],O)==2)A[two[1]]=2*P;
        else A[two[0]]=2*P;
    }
    answer();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0