| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 476680 |
2021-09-28T06:35:08 Z |
KWang31 |
Sob (COCI19_sob) |
Java 11 |
|
1000 ms |
36492 KB |
import java.io.*; import java.util.*;
public class sob{
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
}
public static class Pair implements Comparable<Pair>{
int vtx; int val;
public Pair(int a, int b){
this.vtx=a; this.val=b;
}
public int compareTo(Pair other){
if(this.val<other.val)return -1;
if(this.val>other.val)return 1;
if(this.vtx<other.vtx)return -1;
return 1;
}
}
static int MOD=998244353;
static int[] rk, p,siz;
public static void main(String[] args){
FastReader br=new FastReader();
int N=br.nextInt(); int M=br.nextInt();
int[][] ans=solve(N,M);
for(int i=0; i<N; i++) {
if((ans[i][0]&ans[i][1])!=ans[i][0]) {//The issue is not here
System.out.println("fail"); break;
}
System.out.println(ans[i][0]+" "+ans[i][1]);
}
//StringBuilder sb=new StringBuilder();
//System.out.println(sb.toString());
}
public static int[][] solve(int N, int M){
int[][] ans=new int[N][2];
//Base Case: N=1
if(N==1) {
ans[0][0]=0; ans[0][1]=M;
}else {
if((N&1)==0 && (M&1)==0) {// Case 1: N even
int[][] cur=solve(N/2, M/2);
for(int i=0; i<N/2; i++) {
for(int j=0; j<2; j++) {
ans[2*i+j][0]=cur[i][0]*2+j;
ans[2*i+j][1]=cur[i][1]*2+j;
}
}
}else if((N&1)==0 && (M&1)==1) {
int[][] cur=solve(N/2, (M+1)/2);
for(int i=0; i<N/2; i++) {
for(int j=0; j<2; j++) {
ans[i][j]=cur[i][j]*2;
}
}
int[][] cur2=solve(N/2, (M-1)/2);
for(int i=0; i<N/2; i++) {
for(int j=0; j<2; j++) {
ans[i+N/2][j]=cur2[i][j]*2+1;
}
}
}else if((N&1)==1) {
if((M&1)==0) {
int[][] cur=solve((N+1)/2, M/2);
for(int i=0; i<(N+1)/2; i++){
for(int j=0; j<2; j++) {
ans[i][j]=cur[i][j]*2;
}
}
int[][] cur2=solve((N-1)/2, M/2);
for(int i=0; i<(N-1)/2; i++){
for(int j=0; j<2; j++) {
ans[i+(N+1)/2][j]=cur2[i][j]*2+1;
}
}
}else {
int[][] cur=solve((N+1)/2, (M-1)/2);
//I will pretend M is M-1 in this process
for(int i=0; i<(N+1)/2; i++) {
for(int j=0; j<2; j++) {
ans[i][j]=cur[i][j]*2;
if(ans[i][j]==M-1) {
ans[i][j]=M;
}
}
}
int[][] cur2=solve((N-1)/2, (M+1)/2);
for(int i=0; i<(N-1)/2; i++) {
for(int j=0;j<2;j++) {
ans[i+(N+1)/2][j]=cur2[i][j]*2+1;
}
}
}
}
}
return ans;
}
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
9904 KB |
Output is correct |
| 2 |
Correct |
118 ms |
9564 KB |
Output is correct |
| 3 |
Correct |
145 ms |
9452 KB |
Output is correct |
| 4 |
Execution timed out |
1094 ms |
36492 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
345 ms |
13960 KB |
Output is correct |
| 2 |
Correct |
134 ms |
9364 KB |
Output is correct |
| 3 |
Correct |
129 ms |
9280 KB |
Output is correct |
| 4 |
Correct |
122 ms |
9344 KB |
Output is correct |
| 5 |
Correct |
143 ms |
9448 KB |
Output is correct |
| 6 |
Execution timed out |
1085 ms |
36364 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
9584 KB |
Output is correct |
| 2 |
Correct |
132 ms |
9612 KB |
Output is correct |
| 3 |
Correct |
139 ms |
9504 KB |
Output is correct |
| 4 |
Incorrect |
142 ms |
9504 KB |
Integer parameter [name=x] equals to 322, violates the range [0, 285] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
9904 KB |
Output is correct |
| 2 |
Correct |
118 ms |
9564 KB |
Output is correct |
| 3 |
Correct |
145 ms |
9452 KB |
Output is correct |
| 4 |
Execution timed out |
1094 ms |
36492 KB |
Time limit exceeded |
