QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385569#2830. Data Structureucup-team1209RE 0ms13148kbC++143.3kb2024-04-10 21:19:382024-04-10 21:19:38

Judging History

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

  • [2024-04-10 21:19:38]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:13148kb
  • [2024-04-10 21:19:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 202020

int n,m;
vector<int>st[sz];
vector<int>pos[sz];
set<int>num[3];

vector<pii>ans;
void output() {
    cout<<ans.size()<<'\n';
    for (auto [x,y]:ans) cout<<x<<' '<<y<<'\n';
}
void mov(int f,int t) {
    assert(f!=t);
    assert(st[f].size());
    assert(st[t].size()==0u||(st[t].size()==1u&&st[t][0]==st[f].back()));
    for (auto p:{f,t}) num[st[p].size()].erase(p);
    ans.push_back({f,t});
    int x=st[f].back();
    st[t].push_back(x),st[f].pop_back();
    rep(i,0,1) if (pos[x][i]==f) {pos[x][i]=t; break;}
    num[st[f].size()].insert(f);
    if (st[t].size()!=1u) num[st[t].size()].insert(t);
}
int ok(int x){return pos[x][0]==pos[x][1];}

void check(int x) {
    assert(!ok(x));
    int p0=pos[x][0],p1=pos[x][1];
    if (st[p1].size()==1u) swap(p0,p1);
    if (st[p0].size()==1u) {
        if (st[p1].size()==1u||st[p1][1]==x) {
            mov(p1,p0);
            if (st[p1].size()) check(st[p1][0]);
            return;
        }
        if (num[0].size()) {
            int pp=*(num[0].begin()),t=p1;
            while (233) {
                int y=st[t][1];
                t^=pos[y][0]^pos[y][1];
                if (st[t][1]==y) {
                    int yy=st[t][0];
                    mov(t,pp);
                    check(y);
                    check(yy);
                    return;
                }
            }
        }
    }
}

void work() {
    #define NO return cout<<"-1\n",void()
    rep(i,1,m) st[i].clear();
    rep(i,1,n) pos[i].clear();
    rep(i,0,2) num[i].clear();
    ans.clear();
    rep(i,1,m) {
        int k,x; cin>>k;
        rep(_,1,k) cin>>x,st[i].push_back(x),pos[x].push_back(i);
        if (k!=2||(k==2&&st[i][0]!=st[i][1])) num[k].insert(i);
    }
    if (n==m) {
        if (num[2].size()) NO;
        output();
        return;
    }
    rep(i,1,n) if (!ok(i)) check(i);
    if (num[1].size()||num[2].size()) {
        if (!num[0].size()) NO;
        while (num[1].size()) {
            int p=*(num[1].begin());
            check(st[p][0]);
        }
        assert(num[0].size());
        rep(i,1,n) if (!ok(i)&&st[pos[i][0]][1]==i&&st[pos[i][1]][1]==i) {
            int pp=*(num[0].begin()),p0=pos[i][0],p1=pos[i][1];
            mov(p0,pp),mov(p1,pp);
            check(st[p0].back());
            if (st[p1].size()&&!ok(st[p1][0])) check(st[p1].back());
            if (!num[0].size()) {
                assert(m==n+1);
                NO;
            }
        }
        rep(i,1,n) if (!ok(i)) {
            int pp=*(num[0].begin()),p0=pos[i][0],p1=pos[i][1];
            if (st[p0][1]!=i) swap(p0,p1);
            mov(p0,pp);
            check(st[p0].back());
            assert(num[0].size());
        }
        rep(i,1,n) assert(ok(i));
    }
    output();
}

int main() {
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    while (cin>>n>>m) work();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3
2 1 2
2 1 2
0
1 1
2 1 1
3 4
2 1 3
2 2 3
1 1
1 2

output:

3
1 3
2 3
1 2
0
-1

result:

ok 3 cases passed. max #moves/#balls = 1.500000000

Test #2:

score: 0
Accepted
time: 0ms
memory: 13084kb

input:

1 2
1 1
1 1
1 3
1 1
0
1 1
1 4
1 1
1 1
0
0
1 1
2 1 1
1 2
2 1 1
0
1 3
0
0
2 1 1

output:

1
1 2
1
1 3
1
1 2
0
0
0

result:

ok 6 cases passed. max #moves/#balls = 1.000000000

Test #3:

score: -100
Runtime Error

input:

2 4
1 1
1 2
1 2
1 1
2 5
1 1
1 2
0
1 1
1 2
2 6
0
1 1
0
1 1
1 2
1 2
2 4
1 2
1 1
1 1
1 2
2 5
1 1
0
1 2
1 2
1 1
2 6
1 2
0
1 1
0
1 1
1 2
2 4
1 1
1 2
1 2
1 1
2 5
0
1 2
1 1
1 1
1 2
2 6
1 1
0
1 2
1 2
0
1 1
2 3
2 2 1
1 1
1 2
2 4
2 2 1
1 1
0
1 2
2 5
1 1
0
1 2
2 1 2
0
2 3
1 2
2 1 2
1 1
2 4
1 1
2 2 1
1 2
0
2 5
...

output:


result: