#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "art.h"
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define pp pop_back
#define pf push_front
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
///#define int ll
int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
const int nax = 4001;
int n;
vi adj[nax];
unordered_set<int> vis;
int curcost ;
bool chng = true;
vi res;
/*int rnk[nax];
int publish(vi a)
{
int rep = 0;
for(int i = 0; i < n ; i++)
{
for(int j = 0; j < i ; j++)
rep += (rnk[a[i]] < rnk[a[j]]);
}
return rep;
}
*/
int sup(int x, int g)
{
if(x == g)
return 1;
vis.insert(x);
for(auto e: adj[x])
{
if(vis.count(e) != 0)
continue;
if(sup(e,g) == 1)
return 1;
}
return 0;
}
bool gr(int i, int j, int rema, vi B)
{
vi perm;
int a= B[i], b = B[j];
for(int u = 0; u <= j;u ++)
{
if(u == i)
continue;
perm.pb(B[u]);
}
perm.pb(B[i]);
for(int u = j + 1; u < n; u ++)
perm.pb(B[u]);
int cst = publish(perm) - rema;
/*for(int i = 0; i < n ;i ++)
cout << B[i ] << ' ';
cout << '\n';
for(int i = 0; i < n ;i ++)
cout << perm[i] << ' ' ;
cout << '\n';
cout << a << ' ' << b << ' ' << (cst > curcost) << '\n';
*/
return cst > curcost;
}
vi merge_sort(vi L, int l, int r)
{
int k = (r - l + 1);
if(k == 1)
return L;
vi A = merge_sort(L,l,(l+r)/2);
vi B = merge_sort(A,(l+r)/2+1,r);
int i =l, j = (l+r)/2 + 1;
vi res = B;
int curi = i;
while(curi <= r)
{
if(i > (l+r)/2 || (j <= r && !gr(i,j,(l + r)/2 - i,B)))
res[curi++] = B[j++];
else
res[curi++] = B[i++];
}
curcost = publish(res);
return res;
}
void solve(int N)
{
n = N;
vi perm;
for(int i = 1 ;i <= n; i ++)
perm.pb(i);
curcost = publish(perm);
answer(merge_sort(perm, 0, N - 1));
}
/*
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N; cin >> N;
for(int i = 0; i < N; i ++)
{
int x; cin >> x;
res.pb(x);
rnk[x] = i;
}
vi u = solve(N);
for(auto e: u)
cout << e << ' ' ;
}
*/
Compilation message
art.cpp: In function 'bool gr(int, int, int, vi)':
art.cpp:73:17: warning: unused variable 'a' [-Wunused-variable]
73 | int a= B[i], b = B[j];
| ^
art.cpp:73:26: warning: unused variable 'b' [-Wunused-variable]
73 | int a= B[i], b = B[j];
| ^
interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
20 | if(v.size() != N) {
| ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | if(v.size() != N) {
| ~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Not correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Not correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Not correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Not correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Not correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Not correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
