oj.uz

Submission #68656

# Submission time Handle Problem Language Result Execution time Memory
68656 2018-08-17T19:24:43 Z MANcity Sorting (IOI15_sorting) C++14
0 / 100
 4 ms 2048 KB 
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "sorting.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int t[200002];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int u=0;
    for0(i,N-1)
        if(S[i]!=i)
            u=1;
    if(u==0)
        return 0;
    int l=0;
    int r=(M-1);
    while(1)
    {
        if(l==r)
        {
            pair<int,int> NS[200002];
            int pos[200002];
            for0(i,N-1)
                NS[i]=mp(S[i],i);

            for0(i,l)
            {
                pair<int,int> t=NS[Y[i]];
                NS[Y[i]]=NS[X[i]];
                NS[X[i]]=t;
            }
            for0(i,N-1)
                pos[NS[i].first]=i;
            vector<pair<int,int> > ans;
            for0(i,N-1)
            {
                if(NS[i].first!=i)
                {
                    int t=pos[i];
                    ans.push_back({NS[i].second,NS[t].second});
                    pos[NS[i].first]=t;
                    pos[i]=i;
                    pair<int,int> c=NS[t];
                    NS[t]=NS[i];
                    NS[i]=c;
                }
            }
            int H[200002];
            pos[200002];
            for0(i,N-1)
            {
                H[i]=i;
                pos[i]=i;
            }
            int ff=ans.size()-1;
            for0(i,l)
            {
                pos[H[Y[i]]]=X[i];
                pos[H[X[i]]]=Y[i];
                int t=H[Y[i]];
                H[Y[i]]=H[X[i]];
                H[X[i]]=t;
                P[i]=pos[ans[i].first];
                Q[i]=pos[ans[i].second];
            }
            return (l+1);
        }
        int m=(l+r)/2;
        int NS[200002];
        int pos[200002];
        for0(i,N-1)
            NS[i]=S[i];
        for0(i,m)
        {
            int p=NS[Y[i]];
            NS[Y[i]]=NS[X[i]];
            NS[X[i]]=p;
        }
        for0(i,N-1)
            pos[NS[i]]=i;
        int q=0;
        for0(i,N-1)
        {
            if(NS[i]!=i)
            {
                q++;
                pos[NS[i]]=pos[i];
                NS[pos[i]]=NS[i];
                NS[i]=i;
                pos[i]=i;
            }
        }
        if(q>(m+1))
            l=(m+1);
        else
            r=m;
    }
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:45:31: warning: declaration of 't' shadows a global declaration [-Wshadow]
                 pair<int,int> t=NS[Y[i]];
                               ^
sorting.cpp:24:5: note: shadowed declaration is here
 int t[200002];
     ^
sorting.cpp:56:25: warning: declaration of 't' shadows a global declaration [-Wshadow]
                     int t=pos[i];
                         ^
sorting.cpp:24:5: note: shadowed declaration is here
 int t[200002];
     ^
sorting.cpp:66:23: warning: statement has no effect [-Wunused-value]
             pos[200002];
             ~~~~~~~~~~^
sorting.cpp:72:30: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
             int ff=ans.size()-1;
                    ~~~~~~~~~~^~
sorting.cpp:77:21: warning: declaration of 't' shadows a global declaration [-Wshadow]
                 int t=H[Y[i]];
                     ^
sorting.cpp:24:5: note: shadowed declaration is here
 int t[200002];
     ^
sorting.cpp:72:17: warning: unused variable 'ff' [-Wunused-variable]
             int ff=ans.size()-1;
                 ^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 4 ms 1920 KB Output is correct
5 Incorrect 4 ms 1892 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 4 ms 1920 KB Output is correct
5 Incorrect 4 ms 1892 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Incorrect 4 ms 1920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 4 ms 1920 KB Output is correct
5 Incorrect 4 ms 1892 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2048 KB Output isn't correct
2 Halted 0 ms 0 KB -