oj.uz

Submission #672796

# Submission time Handle Problem Language Result Execution time Memory
672796 2022-12-18T07:36:44 Z jamezzz Sorting (IOI15_sorting) C++17
20 / 100
 1 ms 724 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 200005

int a[maxn],pos[maxn],plate[maxn];

int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]){
    int lo=0,hi=M,mid,res=0;
    while(lo<=hi){
		mid=(lo+hi)>>1;
		//printf("mid: %d\n",mid);
		for(int i=0;i<N;++i)plate[i]=i,a[i]=S[i];
		for(int i=mid-1;i>=0;--i)swap(plate[X[i]],plate[Y[i]]);
		for(int i=0;i<N;++i)pos[plate[i]]=i;
		//printf("pos: ");for(int i=0;i<N;++i)printf("%d ",pos[i]);printf("\n");
		//printf("plate: ");for(int i=0;i<N;++i)printf("%d ",plate[i]);printf("\n");
		vector<pair<int,int>> v;
		for(int i=0;i<N;++i){
			while(plate[i]!=a[i]){
				v.push_back({plate[i],a[i]});
				//printf("swap: %d %d\n",a[i],plate[i]);
				swap(a[i],a[pos[a[i]]]);
			}
		}
		if(v.size()<=mid){
			for(int i=0;i<v.size();++i){
				auto[x,y]=v[i];
				P[i]=pos[x],Q[i]=pos[y];
				int a=plate[X[i]],b=plate[Y[i]];
				swap(pos[a],pos[b]);
				swap(plate[X[i]],plate[Y[i]]);
			}
			for(int i=v.size();i<M;++i){
				P[i]=Q[i]=0;
			}
			hi=mid-1;
			res=mid;
			for(int i=0;i<N;++i){
				assert(plate[i]==i&&pos[i]==i);
			}
		}
		else lo=mid+1;
	}
	return res;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:27:14: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   if(v.size()<=mid){
      |      ~~~~~~~~^~~~~
sorting.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for(int i=0;i<v.size();++i){
      |                ~^~~~~~~~~
sorting.cpp:31:9: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   31 |     int a=plate[X[i]],b=plate[Y[i]];
      |         ^
sorting.cpp:7:5: note: shadowed declaration is here
    7 | int a[maxn],pos[maxn],plate[maxn];
      |     ^
sorting.cpp:35:20: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   35 |    for(int i=v.size();i<M;++i){
      |              ~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -