QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373448 | #2830. Data Structure | PetroTarnavskyi | RE | 2ms | 7660kb | C++20 | 4.3kb | 2024-04-01 17:42:13 | 2024-04-01 17:42:13 |
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))
{
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]] >= 0)
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);
}
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)
{
if(SZ(freeCols) == 0)
{
bad();
return;
}
component.clear();
dfs(i);
solve(component);
}
}
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]++;
solve(component);
}
}
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]++;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5620kb
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: 7660kb
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 ...