QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373458 | #2830. Data Structure | PetroTarnavskyi | WA | 30ms | 7708kb | C++20 | 4.6kb | 2024-04-01 18:02:19 | 2024-04-01 18:02:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 1 << 18;
int n, m;
vector<PII> ans;
VI cols[N];
set<int> freeCols;
VI where[N];
int whereUp(int v)
{
for(int col : where[v])
{
assert(SZ(cols[col]) != 0);
if(cols[col].back() == v)
return col;
assert(cols[col][0] == v);
}
assert(0);
}
void delCol(int v, int col)
{
int id = -1;
FOR(i, 0, SZ(where[v]))
if(where[v][i] == col)
id = i;
assert(id != -1);
where[v] = {where[v][id ^ 1]};
}
void move(int from, int to)
{
assert(from != to);
ans.PB(MP(from, to));
if(SZ(cols[to]) == 0)
freeCols.erase(to);
if(SZ(cols[from]) == 1)
freeCols.insert(from);
int v = cols[from].back();
cols[from].pop_back();
cols[to].PB(v);
delCol(v, from);
where[v].PB(to);
}
bool solve(int v)
{
//cout << v << " " << where[v][0] << " " << where[v][1] << "\n";
//in one col
if(where[v][0] == where[v][1])
return 1;
//cerr << v << "\n";
for(int col : where[v])
assert(cols[col].back() == v);
int id = -1;
FOR(i, 0, 2)
{
if(SZ(cols[where[v][i]]) == 1)
id = i;
}
if(id == -1)
{
if(SZ(freeCols) == 0)
return 0;
int to = *freeCols.begin();
int fr0 = where[v][0];
int fr1 = where[v][1];
move(fr0, to);
move(fr1, to);
}
else
move(where[v][id ^ 1], where[v][id]);
return 1;
}
int cnt[N];
bool solve(VI vs)
{
if(SZ(vs) == 1)
return solve(vs[0]);
//FOR(i, 0, SZ(vs))
// cerr << vs[i] << " ";
//cerr << "\n";
//FOR(i, 0, SZ(vs))
// cerr << cnt[vs[i]] << " ";
//cerr << "\n";
FOR(i, 0, SZ(vs))
{
int j = i;
while(j < SZ(vs) && cnt[vs[j]] <= 0)
j++;
assert(j != SZ(vs));
RFOR(it, j + 1, i)
{
if(!solve(vs[it]))
return 0;
}
i = j;
while(j < SZ(vs) && cnt[vs[j]] >= -1)
j++;
FOR(it, i + 1, j)
{
if(!solve(vs[it]))
return 0;
}
i = j - 1;
}
return 1;
}
VI component;
VI g[N], gr[N];
bool used[N];
void dfs(int v)
{
used[v] = 1;
component.PB(v);
for(int to : g[v])
if(!used[to])
dfs(to);
for(int to : gr[v])
if(!used[to])
dfs(to);
}
void clear()
{
FOR(i, 0, n)
{
g[i].clear();
gr[i].clear();
cnt[i] = used[i] = 0;
where[i].clear();
cols[i].clear();
}
component.clear();
ans.clear();
freeCols.clear();
}
void bad()
{
cout << "-1\n";
clear();
}
void solve()
{
FOR(i, 0, m)
{
if(SZ(cols[i]) != 2)
continue;
int solvedFirst = cols[i][1];
int solvedSecond = cols[i][0];
if(solvedFirst == solvedSecond)
continue;
cnt[solvedFirst]++;
cnt[solvedSecond]--;
g[solvedFirst].PB(solvedSecond);
gr[solvedSecond].PB(solvedFirst);
}
FOR(i, 0, n)
{
if(SZ(g[i]) + SZ(gr[i]) == 0)
{
solve(i);
used[i] = 1;
}
}
FOR(i, 0, n)
{
if(!used[i] && SZ(g[i]) + SZ(gr[i]) == 1)
{
component.clear();
dfs(i);
if(!solve(component))
{
bad();
return;
}
}
}
FOR(i, 0, n)
{
if(!used[i] && cnt[i] > 0)
{
component.clear();
dfs(i);
assert(component[0] == i);
component.erase(component.begin());
if(!solve(i))
{
bad();
return;
}
for(int to : g[i])
cnt[to] = cnt[to] + 1;
if(!solve(component))
{
bad();
return;
}
}
}
FOR(i, 0, n)
{
if(!used[i])
{
assert(cnt[i] == 0);
component.clear();
dfs(i);
if(SZ(freeCols) == 0)
{
bad();
return;
}
assert(component[0] == i);
component.erase(component.begin());
component.PB(i);
move(whereUp(i), *freeCols.begin());
cnt[i]--;
for(int to : g[i])
cnt[to] = cnt[to] + 1;
if(!solve(component))
{
bad();
return;
}
}
}
cout << SZ(ans) << "\n";
for(auto [from, to] : ans)
{
cout << from + 1 << " " << to + 1 << "\n";
}
clear();
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
while(cin >> n >> m)
{
FOR(i, 0, m)
{
int k;
cin >> k;
VI a(k);
FOR(j, 0, k)
{
cin >> a[j];
a[j]--;
where[a[j]].PB(i);
}
if(k == 0)
freeCols.insert(i);
cols[i] = a;
}
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 5912kb
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: 2ms
memory: 5888kb
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: 0
Accepted
time: 0ms
memory: 7708kb
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:
2 1 4 2 3 2 1 4 2 5 2 2 4 5 6 2 2 3 1 4 2 1 5 3 4 2 3 5 1 6 2 1 4 2 3 2 3 4 2 5 2 1 6 3 4 2 1 2 1 3 2 1 2 1 4 2 4 3 1 4 2 2 1 2 3 2 2 1 2 3 2 1 3 1 4 -1 3 2 1 3 1 2 3 3 2 1 4 1 2 4 -1 3 2 3 1 2 1 3 3 1 3 2 1 2 3 1 2 3 1 3 4 1 1 4 0 0 0
result:
ok 27 cases passed. max #moves/#balls = 1.500000000
Test #4:
score: 0
Accepted
time: 2ms
memory: 5628kb
input:
3 6 1 1 1 2 1 2 1 3 1 3 1 1 3 7 1 3 0 1 2 1 2 1 1 1 1 1 3 3 8 0 1 3 1 2 0 1 1 1 1 1 2 1 3 3 6 1 3 1 3 1 2 1 1 1 1 1 2 3 7 1 1 1 3 1 1 1 2 1 2 1 3 0 3 8 1 1 1 2 0 1 3 1 2 0 1 3 1 1 3 6 1 3 1 1 1 2 1 3 1 2 1 1 3 7 1 1 1 2 0 1 1 1 3 1 3 1 2 3 8 1 2 1 1 1 3 1 2 0 1 3 0 1 1 3 6 1 2 1 2 1 3 1 1 1 1 1 3 3 ...
output:
3 1 6 2 3 4 5 3 5 6 3 4 1 7 3 5 6 3 7 2 8 3 4 5 3 6 1 2 3 1 3 4 5 2 6 3 1 8 2 5 4 7 3 2 6 3 5 1 4 3 1 4 2 7 5 6 3 2 8 1 4 3 6 3 4 5 1 2 3 6 3 2 5 4 7 3 6 3 3 4 1 2 5 8 3 1 6 2 5 3 4 3 5 6 1 3 4 7 3 6 7 2 5 4 8 3 1 2 3 6 4 5 3 1 3 5 6 2 7 3 3 7 2 4 6 8 3 1 5 4 6 2 3 3 4 7 1 5 2 3 3 1 6 5 7 4 8 3 4 6 ...
result:
ok 180 cases passed. max #moves/#balls = 1.333333333
Test #5:
score: 0
Accepted
time: 5ms
memory: 5904kb
input:
4 8 1 3 1 3 1 4 1 1 1 2 1 1 1 4 1 2 4 9 1 3 0 1 2 1 1 1 4 1 1 1 4 1 2 1 3 4 10 1 1 1 3 1 3 1 2 1 2 0 1 1 1 4 1 4 0 4 8 1 4 1 3 1 2 1 2 1 1 1 4 1 1 1 3 4 9 1 4 1 3 1 1 1 3 1 4 1 2 1 1 1 2 0 4 10 1 4 1 1 1 2 1 3 0 0 1 2 1 1 1 3 1 4 4 8 1 2 1 4 1 3 1 4 1 2 1 3 1 1 1 1 4 9 1 1 1 4 1 3 1 2 1 3 1 2 0 1 4 ...
output:
4 4 6 5 8 1 2 3 7 4 4 6 3 8 1 9 5 7 4 1 7 4 5 2 3 8 9 4 5 7 3 4 2 8 1 6 4 3 7 6 8 2 4 1 5 4 2 8 3 7 4 9 1 10 4 7 8 1 5 3 6 2 4 4 1 9 4 6 3 5 2 8 4 4 7 2 3 8 10 5 6 4 1 3 4 7 2 8 5 6 4 2 9 1 7 5 6 3 4 4 2 10 1 9 4 5 3 8 4 2 5 1 3 4 8 6 7 4 1 5 3 8 4 9 2 7 4 3 6 2 9 5 7 1 8 4 2 8 6 7 1 5 3 4 4 2 8 6 7...
result:
ok 1575 cases passed. max #moves/#balls = 1.500000000
Test #6:
score: -100
Wrong Answer
time: 30ms
memory: 5680kb
input:
5 10 1 1 1 4 1 2 1 4 1 5 1 2 1 3 1 5 1 1 1 3 5 11 1 1 1 3 1 1 1 2 1 5 1 2 0 1 5 1 4 1 3 1 4 5 12 1 2 0 1 1 1 5 1 2 1 4 1 3 1 4 0 1 5 1 3 1 1 5 10 1 3 1 5 1 1 1 1 1 2 1 4 1 4 1 5 1 2 1 3 5 11 1 3 1 5 1 2 1 2 1 4 1 3 1 1 1 1 0 1 4 1 5 5 12 1 3 1 4 1 2 0 1 5 1 1 1 2 1 1 1 4 1 5 0 1 3 5 10 1 4 1 5 1 3 1...
output:
5 1 9 3 6 7 10 2 4 5 8 5 1 3 4 6 2 10 9 11 5 8 5 3 12 1 5 7 11 6 8 4 10 5 3 4 5 9 1 10 6 7 2 8 5 7 8 3 4 1 6 5 10 2 11 5 6 8 3 7 1 12 2 9 5 10 5 4 7 8 9 3 10 1 5 2 6 5 2 4 1 6 5 7 8 9 3 11 5 1 7 2 3 10 11 8 9 4 5 5 8 10 4 5 6 7 2 9 1 3 5 6 7 1 11 4 5 2 3 8 9 5 2 6 4 11 8 9 1 7 3 10 5 7 8 1 10 4 5 3 ...
result:
wrong answer Should find solution [Case 6652]