#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define ld long double
//#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
ll infl=1000000000000000007;
int inf=2000000007;
int mod=1000000007;
int mod1=998244353;
const int N=1000007;
int a[N][2];
map<int,int>M;
int DP[2*N][2];
int zkad[2*N][2];
bool blocked[2*N][2];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
set<int>S;
int n,m1,m2,t;
cin>>n>>m1>>m2>>t;
S.insert(0);
S.insert(n+1);
for(int i=1;i<=m1;i++)
{
cin>>a[i][0];
S.insert(a[i][0]);
S.insert(a[i][0]-1);
}
for(int i=1;i<=m2;i++)
{
cin>>a[i][1];
S.insert(a[i][1]);
S.insert(a[i][1]-1);
}
int k=0;
vector<int>d={213769420};
for(auto x:S)
{
M[x]=++k;
d.pb(x);
}
for(int i=1;i<=m1;i++) blocked[M[a[i][0]]][0]=1;
for(int i=1;i<=m2;i++) blocked[M[a[i][1]]][1]=1;
for(int j=0;j<2;j++) for(int i=1;i<=k;i++) DP[i][j]=-inf;
DP[1][0]=0;
for(int i=1;i<=k;i++)
{
for(int j=0;j<2;j++)
{
if(!blocked[i][j^1]&&min(t,DP[i][j])>DP[i][j^1])
{
DP[i][j^1]=min(t,DP[i][j]);
zkad[i][j^1]=2;
}
}
for(int j=0;j<2;j++)
{
if(blocked[i+1][j])
{
if(DP[i][j]>=t&&DP[i][j]+1-t>DP[i+1][j])
{
DP[i+1][j]=DP[i][j]+1-t;
zkad[i+1][j]=3;
}
}
else if(DP[i][j]+d[i+1]-d[i]>DP[i+1][j])
{
DP[i+1][j]=DP[i][j]+d[i+1]-d[i];
zkad[i+1][j]=1;
}
}
}
if(DP[k][0]>=0)
{
cout<<"TAK"<<endl;
int i=k,j=0;
vector<int>X;
vector<pair<int,int>>Y;
while(zkad[i][j]!=0)
{
if(zkad[i][j]==1) i--;
else if(zkad[i][j]==2)
{
X.pb(d[i]);
j^=1;
}
else
{
Y.pb({d[i]-DP[i][j],j+1});
i--;
}
}
reverse(all(X));
reverse(all(Y));
cout<<sz(X)<<endl;
for(auto x:X) cout<<x<<" ";
cout<<endl;
cout<<sz(Y)<<endl;
for(auto [x,y]:Y) cout<<x<<" "<<y<<endl;
}
else cout<<"NIE"<<endl;
}
Compilation message
E.cpp: In function 'int main()':
E.cpp:113:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
113 | for(auto [x,y]:Y) cout<<x<<" "<<y<<endl;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Expected Yes or No but "TAK" was found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Expected Yes or No but "TAK" was found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Expected Yes or No but "TAK" was found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Expected Yes or No but "TAK" was found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Expected Yes or No but "TAK" was found |
| 2 |
Halted |
0 ms |
0 KB |
- |
