Submission #485860

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
485860	2021-11-09 14:36:14	MilosMilutinovic	Sorting (IOI15_sorting)	C++14	100 / 100	143 ms	25872 KiB

sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
//jebem ti const glupavi
const int N=601000;
int n,a[N],s[N],pos[N],x[N],y[N];
bool check(int r) {
  rep(i,0,n) a[i]=s[i];
  rep(i,0,r) swap(a[x[i]],a[y[i]]);
  rep(i,0,n) pos[a[i]]=i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sorting.cpp: In function 'int rnd(int)':
sorting.cpp:18:33: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   18 | int rnd(int x) { return mrand() % x;}
      |                         ~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:70:50: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   70 | int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
      |                                             ~~~~~^
sorting.cpp:25:29: note: shadowed declaration is here
   25 | int n,a[N],s[N],pos[N],x[N],y[N];
      |                             ^
sorting.cpp:70:43: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   70 | int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
      |                                      ~~~~~^
sorting.cpp:25:24: note: shadowed declaration is here
   25 | int n,a[N],s[N],pos[N],x[N],y[N];
      |                        ^
sorting.cpp:70:30: warning: declaration of 's' shadows a global declaration [-Wshadow]
   70 | int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
      |                         ~~~~~^
sorting.cpp:25:12: note: shadowed declaration is here
   25 | int n,a[N],s[N],pos[N],x[N],y[N];
      |            ^
sorting.cpp:70:23: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   70 | int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) {
      |                   ~~~~^
sorting.cpp:25:5: note: shadowed declaration is here
   25 | int n,a[N],s[N],pos[N],x[N],y[N];
      |     ^
sorting.cpp:77:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |   int md=l+r>>1;
      |          ~^~

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