Submission #679167

#	Time	Username	Problem	Language	Result	Execution time	Memory
679167		n0sk1ll	Sorting (IOI15_sorting)	C++14	100 / 100	210 ms	23096 KiB

sorting

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

struct disjoint_set_union
{
    vector<int> up;

    void build(int n)
    {
        up.resize(n,-1);
    }

    int Up(int x)
    {
        if (up[x]<0) return x;
        return up[x]=Up(up[x]);
    }

    bool same(int a, int b)
    {
        return Up(a)==Up(b);
    }

    void dsu(int a, int b)
    {
        a=Up(a),b=Up(b);
        if (a==b) return;
        up[a]=b;
    }
};

bool moze(int n, int* S, int m, int *X, int* Y, int* P, int* Q, int okle)
{
    vector<int> p(n);
    ff(i,0,n) p[i]=S[i];
    ff(i,0,okle) swap(p[X[i]],p[Y[i]]);

    disjoint_set_union nesto;
    nesto.build(n);

    int komp=0;
    ff(i,0,n) nesto.dsu(i,p[i]);
    ff(i,0,n) if (nesto.up[i]<0) komp++;
    return komp+okle>=n; //znaci mogu da unitsim svaku (veliku) komponentu >:)
}

bool vi[600005];
vector<int> z[2];

void konstruktuj(int n, int *S, int m, int *X, int *Y, int *P, int *Q, int okle)
{
    vector<int> p(n),gdep(n);
    ff(i,0,n) p[i]=S[i];

    fill(vi,vi+n,false);
	ff(i,0,okle) swap(p[X[i]],p[Y[i]]);
	ff(i,0,n) if(!vi[i]) while(!vi[i]) {vi[i]=true; if(!vi[p[i]]) {z[0].push_back(i); z[1].push_back(p[i]);} i=p[i];}
	ff(i,0,n) gdep[S[i]]=i;
	for(int i=0;i<okle;i++)
	{
		swap(S[X[i]],S[Y[i]]);
		gdep[S[X[i]]]=X[i];
		gdep[S[Y[i]]]=Y[i];
		if(i>=z[0].size()) P[i]=Q[i]=0;
		else
		{
			if(z[0][i]<z[1][i]) swap(z[0][i],z[1][i]);
			P[i]=gdep[z[0][i]];
			Q[i]=gdep[z[1][i]];
			swap(S[P[i]],S[Q[i]]);
			gdep[S[P[i]]]=P[i];
			gdep[S[Q[i]]]=Q[i];

		}
	}
}

int findSwapPairs(int n, int* S, int m, int* X, int* Y, int* P, int* Q)
{
    int l=-1,r=m;
    while (r-l>1)
    {
        int mid=(l+r)/2;
        if (moze(n,S,m,X,Y,P,Q,mid)) r=mid;
        else l=mid;
    }

    konstruktuj(n,S,m,X,Y,P,Q,r);
    return r;
}

Compilation message (stderr)

sorting.cpp: In function 'bool moze(int, int*, int, int*, int*, int*, int*, int)':
sorting.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sorting.cpp:71:5: note: in expansion of macro 'ff'
   71 |     ff(i,0,n) p[i]=S[i];
      |     ^~
sorting.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sorting.cpp:72:5: note: in expansion of macro 'ff'
   72 |     ff(i,0,okle) swap(p[X[i]],p[Y[i]]);
      |     ^~
sorting.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sorting.cpp:78:5: note: in expansion of macro 'ff'
   78 |     ff(i,0,n) nesto.dsu(i,p[i]);
      |     ^~
sorting.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sorting.cpp:79:5: note: in expansion of macro 'ff'
   79 |     ff(i,0,n) if (nesto.up[i]<0) komp++;
      |     ^~
sorting.cpp:68:30: warning: unused parameter 'm' [-Wunused-parameter]
   68 | bool moze(int n, int* S, int m, int *X, int* Y, int* P, int* Q, int okle)
      |                          ~~~~^
sorting.cpp:68:54: warning: unused parameter 'P' [-Wunused-parameter]
   68 | bool moze(int n, int* S, int m, int *X, int* Y, int* P, int* Q, int okle)
      |                                                 ~~~~~^
sorting.cpp:68:62: warning: unused parameter 'Q' [-Wunused-parameter]
   68 | bool moze(int n, int* S, int m, int *X, int* Y, int* P, int* Q, int okle)
      |                                                         ~~~~~^
sorting.cpp: In function 'void konstruktuj(int, int*, int, int*, int*, int*, int*, int)':
sorting.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sorting.cpp:89:5: note: in expansion of macro 'ff'
   89 |     ff(i,0,n) p[i]=S[i];
      |     ^~
sorting.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sorting.cpp:92:2: note: in expansion of macro 'ff'
   92 |  ff(i,0,okle) swap(p[X[i]],p[Y[i]]);
      |  ^~
sorting.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sorting.cpp:93:2: note: in expansion of macro 'ff'
   93 |  ff(i,0,n) if(!vi[i]) while(!vi[i]) {vi[i]=true; if(!vi[p[i]]) {z[0].push_back(i); z[1].push_back(p[i]);} i=p[i];}
      |  ^~
sorting.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sorting.cpp:94:2: note: in expansion of macro 'ff'
   94 |  ff(i,0,n) gdep[S[i]]=i;
      |  ^~
sorting.cpp:100:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   if(i>=z[0].size()) P[i]=Q[i]=0;
      |      ~^~~~~~~~~~~~~
sorting.cpp:86:37: warning: unused parameter 'm' [-Wunused-parameter]
   86 | void konstruktuj(int n, int *S, int m, int *X, int *Y, int *P, int *Q, int okle)
      |                                 ~~~~^

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26