QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #741696 | #9574. Strips | Blizzard | WA | 21ms | 3652kb | C++23 | 6.0kb | 2024-11-13 15:01:52 | 2024-11-13 15:01:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//--------------------------------
#define int long long
#define pii pair<int, int>
#define LL long long
// #define lc p << 1
// #define rc p << 1 | 1
#define lowbit(x) x & (-x)
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
#define Blizzard ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
//-----------------------------------------
void solve()
{
int n, m, k, w;
cin >> n >> m >> k >> w;
vector<int> a(n);
vector<int> b(m);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
sort(b.begin(), b.end());
sort(a.begin(), a.end());
vector<pii> c;
c.push_back(make_pair(0, b[0]));
for (int i = 0; i < m - 1; i++)
c.push_back(make_pair(b[i], b[i + 1]));
c.push_back(make_pair(b[m - 1], w + 1));
int len = c.size();
int p = 0;
// for (int i = 0; i < len; i++)
// cout << c[i].first << ' ' << c[i].second << " \n"[i == c.size() - 1];
vector<int> ans;
for (int i = 0; i < len; i++)
{
vector<int> now;
while (a[p] <= c[i].second)
{
if (a[p] == c[i].first || a[p] == c[i].second)
{
cout << "-1\n";
// cout << a[p] << ' ' << c[i].first << ' ' << c[i].second << '\n';
return;
}
now.push_back(a[p]);
p++;
}
vector<int> gip;
vector<int> nowans;
if (now.size() == 0)
{
continue;
}
// for (int ii = 0; ii < now.size(); ii++)
// cout << now[ii] << " \n"[ii == now.size() - 1];
if (now.size() == 1)
{
if (now[0] + k - 1 < c[i].second)
{
ans.push_back(now[0]);
continue;
}
else
{
if (c[i].second - k <= c[i].first)
{
cout << "-1\n";
return;
}
else
{
// if (c[i].second - 1 == 14)
// cout << c[i].first << ' ' << c[i].second << '\n';
ans.push_back(c[i].second - k);
continue;
}
}
}
if (now[0] + k - 1 >= c[i].second)
{
if (now[0] + k - 1 < c[i].second)
{
ans.push_back(now[0]);
continue;
}
else
{
if (c[i].second - k <= c[i].first)
{
cout << "-1\n";
return;
}
else
{
// if (c[i].second - 1 == 14)
// cout << c[i].first << ' ' << c[i].second << '\n';
ans.push_back(c[i].second - k);
continue;
}
}
}
int preput = now[0];
gip.push_back(now[0] - c[i].first - 1);
int sumgip = now[0] - c[i].first - 1;
int used = 0;
nowans.push_back(now[0]);
for (int ii = 1; ii < now.size(); ii++)
{
if (preput + k - 1 >= now[ii])
{
if (ii == now.size() - 1)
{
for (int jjj = 0; jjj < nowans.size(); jjj++)
ans.push_back(nowans[jjj]);
}
continue;
}
if (now[ii] + k - 1 >= c[i].second)
{
int need = (now[ii] + k - 1) - c[i].second + 1;
// cout << need << '\n';
// cout << sumgip << '\n';
// for (int jj = 0; jj < gip.size(); jj++)
// cout << gip[jj] << " \n"[jj == gip.size() - 1];
if (need > sumgip)
{
cout << "-1\n";
return;
}
int k2 = gip.size() - 1;
int nowuse = 0;
int many = 0;
while (nowuse < need)
{
nowuse += gip[k2];
k2--;
many++;
}
for (int j = 0; j < now.size() && j < now.size() - many - 1; j++)
{
ans.push_back(now[j]);
}
for (int j = 0; j < many; j++)
{
// if (c[i].second - k * (j + 1) == 14)
// {
// cout << "many : " << k << '\n';
// cout << "hi2\n";
// cout << now.size() << "\n";
// cout << c[i].first << ' ' << c[i].second << "\n";
// }
ans.push_back(c[i].second - k * (j + 1));
}
break;
}
gip.push_back(now[ii] - (preput + k - 1 + 1));
sumgip += now[ii] - (preput + k - 1 + 1);
// for (int jjj = 0; jjj < nowans.size(); jjj++)
// {
// cout << nowans[jjj] << " \n"[jjj == nowans.size() - 1];
// cout << "hello\n";
// }
nowans.push_back(now[ii]);
if (ii == now.size() - 1)
{
for (int jjj = 0; jjj < nowans.size(); jjj++)
ans.push_back(nowans[jjj]);
}
}
}
cout << ans.size() << '\n';
for (auto x : ans)
cout << x << ' ';
cout << '\n';
}
signed main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.out", "w", stdout);
Blizzard; // false
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
/*
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
4 5 2 3 16 7 11 2 9 14 13 5 3 2 4 11 6 10 2 1 11 2 1 2 6 1 5 3 2 1 2 6 1 5 2
output:
4 2 7 10 14 -1 2 1 5 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 21ms
memory: 3652kb
input:
11000 3 8 2 53 32 3 33 35 19 38 20 1 30 10 6 7 10 1 42 3 14 4 36 28 40 22 17 20 12 41 27 7 1 19 13 9 6 6 13 78 55 76 53 32 54 58 62 45 21 4 7 61 8 7 3 68 9 26 54 31 22 3 38 65 34 16 58 47 52 29 53 5 8 4 33 33 5 30 6 15 27 12 9 28 19 2 13 10 6 1 2 48 8 12 48 1 41 31 40 7 6 7 61 20 19 30 52 49 17 40 3...
output:
2 3 32 7 3 4 14 22 28 36 40 3 32 48 66 8 3 9 22 26 31 38 54 65 3 5 15 30 -1 3 17 39 49 4 52 67 75 65 1 27 -1 -1 6 24 33 43 48 60 61 3 4 31 33 3 11 20 31 3 3 16 33 3 25 30 42 -1 5 2 6 21 11 33 -1 3 50 59 65 5 50 51 52 67 78 1 81 4 2 11 16 23 6 3 7 17 36 49 61 2 1 45 2 7 25 -1 3 9...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 6)