QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#266637#7738. Equivalent Rewritingcaolima#WA 0ms3528kbC++141.6kb2023-11-26 16:09:492023-11-26 16:09:50

Judging History

你现在查看的是最新测评结果

  • [2023-11-26 16:09:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3528kb
  • [2023-11-26 16:09:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> a(n+5,vector<int>());
    for(int i=1;i<=n;++i){
        int k;
        cin>>k;
        for(int j=0;j<k;++j){
            int t;cin>>t;
            a[i].push_back(t);
        }
    }
    map<int,bool> vis;
    for(int i=n;i>1;--i){
        map<int,int> mp;
        for(auto &j:a[i])mp[j]++;
        for(auto &j:a[i-1])mp[j]++;

        //有没有交集
        bool jiao=0;
        for(auto &[k,v]:mp){
            if(v==2){//出现过两次,有交集
                jiao=1;
                break;
            }
        }
        bool flag=0;
        if(jiao==1){
            for(auto &[k,v]:mp){
                if(v==2&&vis.count(k)==0){//有一个没出现过,不能交换
                    flag=1;
                }
            }
            if(flag==0){//全都出现过,可以交换
                cout<<"Yes"<<endl;
                for(int j=1;j<i-1;++j)cout<<j<<' ';
                cout<<i<<' '<<i-1<<' ';
                for(int j=i+1;j<=n;++j)cout<<j<<' ';
                cout<<endl;
                return ;
            }
        }
        else{//没有交集
            cout<<"Yes"<<endl;
            for(int j=1;j<i-1;++j)cout<<j<<' ';
            cout<<i<<' '<<i-1<<' ';
            for(int j=i+1;j<=n;++j)cout<<j<<' ';
            cout<<endl;
            return ;
        }
        for(auto &[k,v]:mp)vis[k]=1;
    }
    cout<<"No"<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;cin>>t;while(t--)
    solve();

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3528kb

input:

3
3 6
3 3 1 5
2 5 3
2 2 6
2 3
3 1 3 2
2 3 1
1 3
2 2 1

output:

Yes
1 3 2 
No
No

result:

ok OK. (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3524kb

input:

1
10 5
2 2 4
4 1 3 4 2
1 2
3 2 1 4
4 5 2 4 3
3 2 5 4
3 5 4 2
3 1 3 2
5 1 4 2 3 5
1 4

output:

Yes
1 2 3 4 5 6 7 9 8 10 

result:

wrong answer two transactions are not equivalent. (test case 1)