oj.uz

Submission #288668

# Submission time Handle Problem Language Result Execution time Memory
288668 2020-09-01T18:08:10 Z shayan_p Gondola (IOI14_gondola) C++17
90 / 100
 81 ms 13624 KB 
#include<bits/stdc++.h>
#include "gondola.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

const int maxn = 1e5 + 10, mod = 1e9 + 7;

int valid(int n, int inp[]){
    int pos[n];
    fill(pos, pos + n, -1);
    set<int> st;
    for(int i = 0; i < n; i++){	
	--inp[i];
	if(inp[i] < 0)
	    return 0;
	if(st.count(inp[i]))
	    return 0;
	st.insert(inp[i]);	    
	if(inp[i] < n)
	    pos[inp[i]] = i;
    }
    int lst = -1;
    for(int i = 0; i < n; i++){
	if(pos[i] != -1){
	    if(lst == -1)
		lst = i;
	    if((lst - i + n) % n != (pos[lst] - pos[i] + n) % n)
		return 0;
	}
    }
    for(int i = 0; i < n; i++){
	if(pos[i] != -1){
	    if(lst == -1)
		lst = i;
	    if((lst - i + n) % n != (pos[lst] - pos[i] + n) % n)
		return 0;
	}
    }
    return 1;
}
int replacement(int n, int inp[], int outp[]){
    const int maxl = 3e5 + 10;
    int pos[maxl], arr[n];
    memset(pos, -1, sizeof pos);
    int start = 0;
    for(int i = 0; i < n; i++){
	pos[--inp[i]] = i;
	if(inp[i] < n)
	    start = (i - inp[i] + n) % n;
    }
    for(int i = 0; i < n; i++){
	arr[(i + start) % n] = i;
    }
    
    set<int> fre;
    for(int i = 0; i < n; i++){
	if(inp[i] >= n)
	    fre.insert(i);
    }
    int L = 0;
    for(int i = n; i < maxl; i++){
	if(pos[i] == -1){
	    if(fre.empty())
		break;
	    int x = *fre.begin();
	    outp[L++] = arr[x] + 1;
	    arr[x] = i;
	}
	else{
	    fre.erase(pos[i]);
	    int x = pos[i];
	    outp[L++] = arr[x] + 1;
	    arr[x] = i;	    
	}
    }
    return L;
}
int countReplacement(int n, int inp[]){
    int chert[n + 10];
    for(int i = 0; i < n; i++)
	chert[i] = inp[i];
    if(!valid(n, chert))
    	return 0;

    const int mod = 1e9 + 9;
    const int maxl = 3e5 + 10;
    int pos[maxl], arr[n];
    memset(pos, -1, sizeof pos);
    int ans = 1;
    int start = -1;
    for(int i = 0; i < n; i++){
	pos[--inp[i]] = i;
	if(inp[i] < n)
	    start = (i - inp[i] + n) % n;
    }
    if(start == -1)
	ans = n;
    
    set<int> fre;
    for(int i = 0; i < n; i++){
	if(inp[i] >= n)
	    fre.insert(i);
    }
    for(int i = n; i < maxl; i++){
	if(pos[i] == -1){
	    if(fre.empty())
		break;
	    ans = 1ll * ans * sz(fre) % mod;
	}
	else{
	    fre.erase(pos[i]);
	}
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:97:20: warning: unused variable 'arr' [-Wunused-variable]
   97 |     int pos[maxl], arr[n];
      |                    ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 16 ms 2432 KB Output is correct
7 Correct 13 ms 1024 KB Output is correct
8 Correct 33 ms 4220 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 39 ms 4856 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 19 ms 2432 KB Output is correct
7 Correct 16 ms 1024 KB Output is correct
8 Correct 33 ms 4220 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 39 ms 4984 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 21 ms 2176 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 54 ms 4984 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct
8 Correct 2 ms 1536 KB Output is correct
9 Correct 2 ms 1536 KB Output is correct
10 Correct 2 ms 1536 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 2 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct
8 Correct 2 ms 1536 KB Output is correct
9 Correct 2 ms 1536 KB Output is correct
10 Correct 2 ms 1536 KB Output is correct
11 Correct 13 ms 2048 KB Output is correct
12 Correct 15 ms 2160 KB Output is correct
13 Correct 29 ms 3840 KB Output is correct
14 Correct 13 ms 2048 KB Output is correct
15 Correct 31 ms 4216 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1568 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct
8 Correct 1 ms 1536 KB Output is correct
9 Correct 73 ms 5880 KB Output is correct
10 Correct 55 ms 5112 KB Output is correct
11 Correct 21 ms 2816 KB Output is correct
12 Correct 26 ms 3072 KB Output is correct
13 Correct 7 ms 1920 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct
8 Correct 1 ms 1536 KB Output is correct
9 Correct 81 ms 5732 KB Output is correct
10 Correct 54 ms 5112 KB Output is correct
11 Correct 21 ms 2816 KB Output is correct
12 Correct 26 ms 3192 KB Output is correct
13 Correct 7 ms 1920 KB Output is correct
14 Runtime error 65 ms 13624 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -