| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 119927 |
2019-06-22T16:30:53 Z |
tutis |
Trapezi (COI17_trapezi) |
C++17 |
|
500 ms |
103728 KB |
/*input
5
00000000000
0000000000000
0000000.0000000
000..0000.0000000
00.0.00000.00000.0.
00.000000000000.000
00000000000000000
0000000.000...0
0000000000000
00000000000
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct grupe
{
int x, y, z;
bool reikia = false;
};
struct BitSet
{
unsigned long long x, y, z;
BitSet operator~()
{
BitSet ret;
ret.x = ~x;
ret.y = ~y;
ret.z = ~z;
return ret;
}
bool operator<(const BitSet &o)const
{
return (x ^ y ^ z) < (o.x ^ o.y ^ o.z);
}
bool operator==(const BitSet &o)const
{
return (x ^ y ^ z) == (o.x ^ o.y ^ o.z);
}
BitSet operator&(const BitSet &other)
{
BitSet ret;
ret.x = x & other.x;
ret.y = y & other.y;
ret.z = z & other.z;
return ret;
}
void set(int i)
{
if (i < 64)
{
x |= (1ull << i);
}
else if (i < 128)
{
y |= (1ull << (i - 64));
}
else
{
z |= (1ull << (i - 128));
}
}
void unset(int i)
{
if (i < 64)
{
x &= ~(1ull << i);
}
else if (i < 128)
{
y &= ~(1ull << (i - 64));
}
else
{
z &= ~(1ull << (i - 128));
}
}
bool get(int i)
{
if (i < 64)
{
return (x & (1ull << (i))) != 0;
}
else if (i < 128)
{
return (y & (1ull << (i - 64))) != 0;
}
else
{
return (z & (1ull << (i - 128))) != 0;
}
}
};
vector<grupe>xx;
vector<char>col;
BitSet x;
BitSet prad;
int timer = 0;
vector<int>jj[150];
bitset<390>xxxxx;
struct custom
{
size_t operator()(const BitSet&x)const
{
unsigned long long h = x.x ^ x.y ^ x.z;
return h ^ (h >> 32);
}
};
unordered_map<BitSet, bitset<390>, custom>M;
unordered_set<BitSet, custom>buvau[150];
int n;
int riba;
void ieskom(int i)
{
if (i > riba || buvau[i].count(x))
return;
buvau[i].insert(x);
M[x] = xxxxx;
if (x.get(i) == false)
return ieskom(i + 1);
for (int j : jj[i])
{
if (x.get(xx[j].x) && x.get(xx[j].y) && x.get(xx[j].z))
{
x.unset(xx[j].x);
x.unset(xx[j].y);
x.unset(xx[j].z);
xxxxx[j] = true;
ieskom(i + 1);
xxxxx[j] = false;
x.set(xx[j].x);
x.set(xx[j].y);
x.set(xx[j].z);
}
}
}
bool ieskom1(int i)
{
M[x] = xxxxx;
BitSet y = (~x)&prad;
if (M.count(y))
{
auto xxx = M[y];
for (int i = 0; i < (int)xx.size(); i++)
if (xxx[i])
xx[i].reikia = true;
return true;
}
if (i < riba)
return false;
if (x.get(i) == false)
return ieskom1(i - 1);
for (int j : jj[i])
{
if (x.get(xx[j].x) && x.get(xx[j].y) && x.get(xx[j].z))
{
x.unset(xx[j].x);
x.unset(xx[j].y);
x.unset(xx[j].z);
xx[j].reikia = true;
if (ieskom1(i - 1))
return true;
xx[j].reikia = false;
x.set(xx[j].x);
x.set(xx[j].y);
x.set(xx[j].z);
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin >> n;
string s[2 * n];
for (int i = 0; i < 2 * n; i++)
cin >> s[i];
vector<int>id[2 * n];
col = vector<char>(6 * n * n);
vector<pair<int, int>>xy;
for (int i = 0; i < 2 * n; i++)
for (int t = 0; t < (int)s[i].size(); t++)
{
xy.push_back({i, t});
id[i].push_back(0);
}
for (auto it : xy)
id[it.first][it.second] = timer++;
for (int i = 0; i < 2 * n; i++)
for (int t = 0; t < (int)s[i].size(); t++)
{
col[id[i][t]] = s[i][t];
}
riba = timer / 2;
vector<int>adj[timer];
for (int i = 0; i < 2 * n; i++)
{
for (int t = 0; t + 1 < (int)id[i].size(); t++)
{
int x = id[i][t];
int y = id[i][t + 1];
adj[x].push_back(y);
adj[y].push_back(x);
}
}
for (int i = 0; i <= n - 2; i++)
{
for (int t = 0; t < (int)id[i].size(); t += 2)
{
int x = id[i][t];
int y = id[i + 1][t + 1];
adj[x].push_back(y);
adj[y].push_back(x);
}
}
for (int t = 0; t < (int)id[n - 1].size(); t += 2)
{
int x = id[n - 1][t];
int y = id[n][t];
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = n + 1; i < 2 * n; i++)
{
for (int t = 0; t < (int)id[i].size(); t += 2)
{
int x = id[i][t];
int y = id[i - 1][t + 1];
adj[x].push_back(y);
adj[y].push_back(x);
}
}
for (int i = 0; i < timer; i++)
{
for (int j : adj[i])
{
for (int k : adj[i])
{
if (j < k)
{
grupe a;
a.x = i;
a.y = j;
a.z = k;
xx.push_back(a);
}
}
}
}
for (int i = 0; i < (int)xx.size(); i++)
{
jj[xx[i].x].push_back(i);
jj[xx[i].y].push_back(i);
jj[xx[i].z].push_back(i);
}
for (int i = 0; i < 2 * n; i++)
{
for (int t = 0; t < (int)id[i].size(); t++)
{
if (s[i][t] == '0')
x.set(id[i][t]);
}
}
prad = x;
ieskom(0);
if (ieskom1(timer - 1))
{
for (grupe a : xx)
{
if (a.reikia == false)
continue;
set<int>aplink;
for (int i : {a.x, a.y, a.z})
for (int j : adj[i])
aplink.insert(j);
for (int i : {a.x, a.y, a.z})
aplink.erase(i);
set<char>cols;
for (int i : aplink)
cols.insert(col[i]);
for (char x = '1'; x <= '6'; x++)
if (cols.count(x) == 0)
{
col[a.x] = x;
col[a.y] = x;
col[a.z] = x;
}
}
for (int i = 0; i < 2 * n; i++)
{
for (int t = 0; t < (int)id[i].size(); t++)
{
cout << col[id[i][t]];
}
cout << '\n';
}
}
else
cout << "nemoguce\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
896 KB |
Output is correct |
| 2 |
Correct |
24 ms |
4984 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1536 KB |
Output is correct |
| 6 |
Correct |
4 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
103728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
